首页 > 代码库 > 【权值分块】bzoj3224 Tyvj 1728 普通平衡树
【权值分块】bzoj3224 Tyvj 1728 普通平衡树
权值分块和权值线段树的思想一致，离散化之后可以代替平衡树的部分功能。
部分操作的时间复杂度：
| 插入 | 删除 | 全局排名 | 全局K大 | 前驱 | 后继 | 全局最值 |
| O(1) | O(1) | 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 }
【权值分块】bzoj3224 Tyvj 1728 普通平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。