【权值分块】bzoj3224 Tyvj 1728 普通平衡树

权值分块和权值线段树的思想一致，离散化之后可以代替平衡树的部分功能。

部分操作的时间复杂度：

插入	删除	全局排名	全局K大	前驱	后继	全局最值	按值域删除元素
O(1)	O(1)	O(sqrt(n))	O(sqrt(n))	O(sqrt(n))	O(sqrt(n))	O(sqrt(n))	O(sqrt(n))(懒标记)

当然，因为要离散化，所以只能离线。

代码很短，很快，比我的Splay短一倍，快一倍，现在在bzoj上rank6。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 using namespace std;
 5 #define N 100001
 6 struct Point{int v,p;}t[N];
 7 bool operator < (const Point &a,const Point &b){return a.v<b.v;}
 8 int n,op[N],a[N],ma[N],en,l[800],r[800],sumv[800],sz,sum,num[N],b[N],Num,CH[12];
 9 inline void R(int &x){
10     char c=0;int f=1;
11     for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
12     for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
13     x*=f;
14 }
15 inline void P(int x)
16 {
17     if(!x){putchar('0');puts("");return;}
18     if(x<0){putchar('-');x=-x;}Num=0;
19     while(x>0)CH[++Num]=x%10,x/=10;
20     while(Num)putchar(CH[Num--]+48);puts("");
21 }
22 void makeblock()
23 {
24     sz=sqrt(en); if(!sz) sz=1;
25     for(sum=1;sum*sz<n;sum++)
26       {
27           l[sum]=r[sum-1]+1;
28           r[sum]=sz*sum;
29           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
30       }
31     l[sum]=r[sum-1]+1;
32     r[sum]=n;
33     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
34 }
35 inline void Insert(const int &x){b[x]++; sumv[num[x]]++;}
36 inline void Delete(const int &x){b[x]--; sumv[num[x]]--;}
37 inline int Rank(const int &x)
38 {
39     int cnt=0;
40     for(int i=1;i<num[x];i++) cnt+=sumv[i];
41     for(int i=l[num[x]];i<x;i++) cnt+=b[i];
42     return cnt+1;
43 }
44 inline int Kth(const int &x)
45 {
46     int cnt=0;
47     for(int i=1;;i++)
48       {
49           cnt+=sumv[i];
50           if(cnt>=x)
51             {
52                 cnt-=sumv[i];
53             for(int j=l[i];;j++)
54                 {cnt+=b[j]; if(cnt>=x) return j;}
55             }
56       }
57 }
58 inline int Next(const int &x)
59 {
60     for(int i=x+1;i<=r[num[x]];i++) if(b[i]) return i;
61     for(int i=num[x]+1;;i++) if(sumv[i])
62       for(int j=l[i];;j++)
63         if(b[j]) return j;
64 }
65 inline int Pre(const int &x)
66 {
67     for(int i=x-1;i>=l[num[x]];i--) if(b[i]) return i;
68     for(int i=num[x]-1;;i--) if(sumv[i])
69       for(int j=r[i];;j--)
70         if(b[j]) return j;
71 }
72 int main()
73 {
74     R(n); for(int i=1;i<=n;i++)
75       {
76           R(op[i]); R(t[i].v);
77           t[i].p=i;
78       }
79     sort(t+1,t+n+1);
80     ma[a[t[1].p]=++en]=t[1].v;
81     for(int i=2;i<=n;i++)
82       {
83           if(t[i].v!=t[i-1].v) en++;
84           ma[a[t[i].p]=en]=t[i].v;
85       }
86     makeblock();
87     for(int i=1;i<=n;i++)
88       {
89           if(op[i]==1) Insert(a[i]);
90           else if(op[i]==2) Delete(a[i]);
91           else if(op[i]==3) P(Rank(a[i]));
92           else if(op[i]==4) P(ma[Kth(ma[a[i]])]);
93           else if(op[i]==5) P(ma[Pre(a[i])]);
94           else P(ma[Next(a[i])]);
95       }
96     return 0;
97 }