BZOJ 3166

太过爱你忘了你带给我的痛 2021-12-04 06:59 252阅读 0赞

# BZOJ3196: Tyvj 1730 二逼平衡树 #

传送门：[https://www.lydsy.com/JudgeOnline/problem.php?id=3196][https_www.lydsy.com_JudgeOnline_problem.php_id_3196]

题意：

1.查询k在区间内的排名  
2.查询区间内排名为k的值  
3.修改某一位值上的数值  
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)  
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

树套树模板题，在TLE的边缘疯狂试探

/**************************************************************     Problem: 3196     User: buerdepepeqi     Language: C++     Result: Accepted     Time:9660 ms     Memory:73172 kb ****************************************************************/   #include<iostream> #include<cstdlib> #include<cstdio> #define inf 100000000 #define N 200001 #define M 3000001 using namespace std; int n,m,sz,tmp,a[N]; int ls[M],rs[M],rnd[M],v[M],s[M],w[M]; int root[N]; void update(int k) {s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;} void insert(int &k,int num) {     if(!k){k=++sz;s[k]=w[k]=1;v[k]=num;rnd[k]=rand();return;}     s[k]++;     if(num==v[k])w[k]++;     else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);}     else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void del(int &k,int num) {     if(v[k]==num)     {         if(w[k]>1){w[k]--;s[k]--;return;}         if(ls[k]*rs[k]==0)k=ls[k]+rs[k];         else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);}         else {lturn(k);del(k,num);}     }     else if(num<v[k])        {del(ls[k],num);s[k]--;}     else {del(rs[k],num);s[k]--;} } void build(int k,int l,int r,int x,int num) {     insert(root[k],num);     if(l==r)return;     int mid=(l+r)>>1;     if(x<=mid)build(k<<1,l,mid,x,num);     else build(k<<1|1,mid+1,r,x,num); } void ask_rank(int k,int num) {     if(!k)return;     if(num==v[k]){tmp+=s[ls[k]];return;}     else if(num<v[k])ask_rank(ls[k],num);     else {tmp+=s[ls[k]]+w[k];ask_rank(rs[k],num);} } void get_rank(int k,int l,int r,int x,int y,int num) {     if(l==x&&r==y){ask_rank(root[k],num);return;}     int mid=(l+r)>>1;     if(mid>=y)get_rank(k<<1,l,mid,x,y,num);     else if(mid<x)get_rank(k<<1|1,mid+1,r,x,y,num);     else     {         get_rank(k<<1,l,mid,x,mid,num);         get_rank(k<<1|1,mid+1,r,mid+1,y,num);     } } void get_index(int x,int y,int z) {     int l=0,r=inf,ans;     while(l<=r)     {         int mid=(l+r)>>1;         tmp=1;get_rank(1,1,n,x,y,mid);         if(tmp<=z){l=mid+1;ans=mid;}         else r=mid-1;         }     printf("%d\n",ans); } void change(int k,int l,int r,int x,int num,int y) {     del(root[k],y);     insert(root[k],num);     if(l==r)return;     int mid=(l+r)>>1;     if(x<=mid)change(k<<1,l,mid,x,num,y);     else change(k<<1|1,mid+1,r,x,num,y); } void before(int k,int num) {     if(!k)return;     if(v[k]<num){tmp=max(v[k],tmp);before(rs[k],num);}     else before(ls[k],num); } void after(int k,int num) {     if(!k)return;     if(v[k]>num){tmp=min(v[k],tmp);after(ls[k],num);}     else after(rs[k],num); } void ask_after(int k,int l,int r,int x,int y,int num) {     if(l==x&&r==y){after(root[k],num);return;}     int mid=(l+r)>>1;     if(mid>=y)ask_after(k<<1,l,mid,x,y,num);     else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num);     else     {         ask_after(k<<1,l,mid,x,mid,num);         ask_after(k<<1|1,mid+1,r,mid+1,y,num);     } } void ask_before(int k,int l,int r,int x,int y,int num) {     if(l==x&&r==y){before(root[k],num);return;}     int mid=(l+r)>>1;     if(mid>=y)ask_before(k<<1,l,mid,x,y,num);     else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num);     else     {         ask_before(k<<1,l,mid,x,mid,num);         ask_before(k<<1|1,mid+1,r,mid+1,y,num);     } } int main() {     scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++)scanf("%d",&a[i]);     for(int i=1;i<=n;i++)build(1,1,n,i,a[i]);     for(int i=1;i<=m;i++)     {         int f;scanf("%d",&f);         int x,y,k;         switch(f)         {             case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break;             case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break;             case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break;             case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break;             case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break;          }     }     return 0; }

转载于:https://www.cnblogs.com/buerdepepeqi/p/10841366.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_3196]: https://www.lydsy.com/JudgeOnline/problem.php?id=3196