泥是不是啥叼,这种题现在才做
是是是,您教导的是
传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3196
这题怎么套都可以吧。。线段树套平衡树,线段树套线段树,平衡树套平衡树?
然而我并没这样写,我写浪一点直接就树状数组套权值线段树上了
似乎$rank$靠前的都是这个?或许有什么特技吧
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define N 50005 struct tree{tree*l,*r;int cnt;}*T[N],C[N*200],*c=C,*L[33],*R[33]; int i,j,m,n,x,y,M,f[N],l[N],r[N],k[N],a[N],hs[N<<1]; #define nc() getchar() inline int read(){ int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc()); if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f; } #define lson o->l,l,m #define rson o->r,m+1,r void add(tree*&o,int l,int r,int v,int f){ if(o==NULL)o=++c;o->cnt+=f;if(l==r)return;int m=l+r>>1; v<=m?add(lson,v,f):add(rson,v,f); } inline void Add(int x,int d,int f){for(;x<=n;x+=x&-x)add(T[x],1,M,d,f);} inline int askkth(int x,int y,int l,int r,int v){ int h=0,t=0,rr=r,ll=l-1,k=0,ar=0,al=0,i,m=x+y>>1; for(;rr;rr-=rr&-rr)R[++t]=T[rr]; for(;ll;ll-=ll&-ll)L[++h]=T[ll]; for(;x<y;m=x+y>>1)if(v>m){ for(ar=0,i=1;i<=t;R[i]=R[i]->r,++i){ if(R[i]->l!=NULL)ar+=R[i]->l->cnt; if(R[i]->r==NULL)R[i]->r=++c; } for(al=0,i=1;i<=h;L[i]=L[i]->r,++i){ if(L[i]->l!=NULL)al+=L[i]->l->cnt; if(L[i]->r==NULL)L[i]->r=++c; } k+=ar-al,x=m+1; }else{ for(i=1;i<=t;R[i]=R[i]->l,++i)if(R[i]->l==NULL)R[i]->l=++c; for(i=1;i<=h;L[i]=L[i]->l,++i)if(L[i]->l==NULL)L[i]->l=++c;y=m; } return k+1; } inline int askknm(int x,int y,int l,int r,int k){ int h=0,t=0,rr=r,ll=l-1,ar=0,al=0,i,m=x+y>>1,sm=0; for(;rr;rr-=rr&-rr)R[++t]=T[rr]; for(;ll;ll-=ll&-ll)L[++h]=T[ll]; for(;x<y&&k;m=x+y>>1){ for(ar=0,i=1;i<=t;++i)if(R[i]->l!=NULL)ar+=R[i]->l->cnt; for(al=0,i=1;i<=h;++i)if(L[i]->l!=NULL)al+=L[i]->l->cnt; if(ar-al>=k){ for(i=1;i<=t;R[i]=R[i]->l,++i)if(R[i]->l==NULL)R[i]->l=++c; for(i=1;i<=h;L[i]=L[i]->l,++i)if(L[i]->l==NULL)L[i]->l=++c;y=m; }else{ for(i=1;i<=t;R[i]=R[i]->r,++i)if(R[i]->r==NULL)R[i]->r=++c; for(i=1;i<=h;L[i]=L[i]->r,++i)if(L[i]->r==NULL)L[i]->r=++c;x=m+1,k-=ar-al; } } return x; } int main(){ for(n=read(),m=read(),i=1;i<=n;++i)a[i]=read(),hs[++*hs]=a[i]; for(i=1;i<=m;++i){ f[i]=read(); if(f[i]!=3&&f[i]!=2)l[i]=read(),r[i]=read(),k[i]=read(),hs[++*hs]=k[i]; else if(f[i]==3)l[i]=read(),k[i]=read(),hs[++*hs]=k[i]; else l[i]=read(),r[i]=read(),k[i]=read(); } sort(hs+1,hs+*hs+1),M=unique(hs+1,hs+*hs+1)-hs-1; for(i=1;i<=n;++i)a[i]=lower_bound(hs+1,hs+M+1,a[i])-hs; for(i=1;i<=m;++i)if(f[i]!=3&&f[i]!=2)k[i]=lower_bound(hs+1,hs+M+1,k[i])-hs; else if(f[i]==3)k[i]=lower_bound(hs+1,hs+M+1,k[i])-hs; for(i=1;i<=n;++i)Add(i,a[i],1); for(i=1;i<=m;++i){ if(f[i]==1)printf("%d\n",askkth(1,M,l[i],r[i],k[i])); if(f[i]==2)printf("%d\n",hs[askknm(1,M,l[i],r[i],k[i])]); if(f[i]==3)Add(l[i],a[l[i]],-1),Add(l[i],k[i],1),a[l[i]]=k[i]; if(f[i]==4)printf("%d\n",hs[askknm(1,M,l[i],r[i],askkth(1,M,l[i],r[i],k[i])-1)]); if(f[i]==5)printf("%d\n",hs[askknm(1,M,l[i],r[i],askkth(1,M,l[i],r[i],k[i]+1))]); } }
$loading...$
2023年4月14日 18:23
I learned a lot from the insight you shared here. It's good to learn more about this topic, and if you have some free time or you're curious about some celebrity basic information, you can visit celeb networth post and search for it.