3196: Tyvj 1730 二逼平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2271 Solved: 935
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
Input
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继
Output
对于操作1,2,4,5各输出一行，表示查询结果
Sample Input
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
Sample Output
2
4
3
4
9
4
3
4
9
HINT
1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数
Source
Solution
树套树，线段树套平衡树 其实也可以写 权值线段树套区间线段树
正确姿势就是，对于区间建一颗线段树，线段树的每个区间都建一颗平衡树，对于区间的询问，从线段树上找区间，利用平衡树去询问
操作一：查询区间中的小于K的值，最后+1
操作二：二分判定，代入操作一
操作三：对于包含的每个区间上的pos都修改
操作四：对于每段都查询前驱，最后找到最大的前驱
操作五：对于每段都查询后继，最后找到最小的后继
启发：
认真背模板！！！一条语句的错误浪费了自己和别人很长时间
数据结构题要多练多总结，多调多背
要坚定不移的相信自己是智障，新东西一昧想YY不愿了解别人的方法，就是在作死
大代码题要面向对象编程,合理分成程序段,方便差错和调试
Code
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int read() { int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } #define maxn 2000100 int n,m,a[maxn],maxx; //SplayTree----------------------------------------------------------------------------------------- int fa[maxn],son[maxn][2],key[maxn],cnt[maxn],size[maxn],root[maxn],sz; void clear(int now){son[now][1]=son[now][0]=fa[now]=cnt[now]=key[now]=size[now]=0;} int get(int now){return son[fa[now]][1]==now;} void update(int now) { if (!now) return; size[now]=cnt[now]; if (son[now][0]) size[now]+=size[son[now][0]]; if (son[now][1]) size[now]+=size[son[now][1]]; } void rotate(int x) { int y=fa[x],z=fa[y],which=get(x); son[y][which]=son[x][which^1]; fa[son[y][which]]=y; fa[y]=x; son[x][which^1]=y; fa[x]=z; if (z) son[z][son[z][1]==y]=x; update(y); update(x); } void splay(int rt,int x,int tar) { for (int f; (f=fa[x])!=tar; rotate(x)) if (fa[f]!=tar) rotate(get(x)==get(f)?f:x); if (tar==0) root[rt]=x; } void insert(int rt,int v) { if (!root[rt]) {sz++;son[sz][0]=son[sz][1]=fa[sz]=0;key[sz]=v;size[sz]=1;cnt[sz]=1;root[rt]=sz;return;} int now=root[rt],f=0; while (now) { if (key[now]==v) {cnt[now]++;update(now);update(f);splay(rt,now,0);break;} f=now; now=son[now][key[now]<v]; if (now==0) { sz++;son[sz][0]=son[sz][1]=0;key[sz]=v;size[sz]=1; cnt[sz]=1;fa[sz]=f;son[f][key[f]<v]=sz; update(f);splay(rt,sz,0);break; } } } int find(int rt,int x) { int now=root[rt]; while (now) { if (key[now]==x) return now; if (key[now]>x) now=son[now][0]; else now=son[now][1]; } } int findrank(int rt,int x) { int now=root[rt],ans=0; while (now) { if (key[now]>x) now=son[now][0]; else if (key[now]<x) ans+=(cnt[now]+size[son[now][0]]),now=son[now][1]; else {ans+=size[son[now][0]];break;} } return ans; } int findkth(int rt,int x) { int now=root[rt]; while (now) { if (son[now][0] && x<=size[son[now][0]]) now=son[now][0]; else { int temp; if (son[now][0]) temp=size[son[now][0]]+cnt[now]; else temp=cnt[now]; if (x<=temp) return key[now]; x-=temp; now=son[now][1]; } } } int prev(int rt) { int now=son[root[rt]][0]; while (son[now][1]) now=son[now][1]; return now; } bool remove(int rt,int now) { int fi=find(rt,now); if (fi==-1) return false; else splay(rt,fi,0); if (cnt[root[rt]]>1) {cnt[root[rt]]--; size[root[rt]]--; return true;}; if (!son[root[rt]][0] && !son[root[rt]][1]) {clear(root[rt]); root[rt]=0; return true;} if (!son[root[rt]][0]) {int oldroot=root[rt]; root[rt]=son[root[rt]][1]; fa[root[rt]]=0; clear(oldroot); return true;} else if (!son[root[rt]][1]) {int oldroot=root[rt]; root[rt]=son[root[rt]][0]; fa[root[rt]]=0; clear(oldroot); return true;} int leftbig=prev(rt),oldroot=root[rt]; splay(rt,leftbig,0); fa[son[oldroot][1]]=root[rt]; son[root[rt]][1]=son[oldroot][1]; clear(oldroot); update(root[rt]); return true; } int Prev(int rt,int x) { int now=root[rt],ans=-0x7fffffff; while (now) { if (key[now]<x) {if (ans<key[now])ans=key[now]; now=son[now][1];} else now=son[now][0]; } return ans; } int Succ(int rt,int x) { int now=root[rt],ans=0x7fffffff; while (now) { if (key[now]>x) {if (ans>key[now]) ans=key[now]; now=son[now][0];} else now=son[now][1]; } return ans; } //SegmentTree--------------------------------------------------------------------------------------- void buildTree(int now,int l,int r) { for (int i=l; i<=r; i++) insert(now,a[i]); if (l==r) return; int mid=(l+r)>>1; buildTree(now<<1,l,mid); buildTree(now<<1|1,mid+1,r); } int FindRank(int now,int l,int r,int L,int R,int rk) { if (L<=l && R>=r) return findrank(now,rk); int mid=(l+r)>>1,rak=0; if (L<=mid) rak+=FindRank(now<<1,l,mid,L,R,rk); if (mid<R) rak+=FindRank(now<<1|1,mid+1,r,L,R,rk); return rak; } int FindKth(int L,int R,int kt) { int ll=0,rr=maxx,mid; while (ll<rr) { mid=(ll+rr)>>1; if (FindRank(1,1,n,L,R,mid)<kt) ll=mid+1; else rr=mid; } return ll-1; } void ChangeK(int now,int l,int r,int p,int k) { remove(now,a[p]); insert(now,k); if (l==r) {a[p]=k;return;} int mid=(l+r)>>1; if (p<=mid) ChangeK(now<<1,l,mid,p,k); else ChangeK(now<<1|1,mid+1,r,p,k); } int GetPrev(int now,int l,int r,int L,int R,int k) { int mid=(l+r)>>1,pre=-0x7fffffff; if (L<=l && R>=r) return Prev(now,k); if (L<=mid) pre=max(pre,GetPrev(now<<1,l,mid,L,R,k)); if (mid<R) pre=max(pre,GetPrev(now<<1|1,mid+1,r,L,R,k)); return pre; } int GetSucc(int now,int l,int r,int L,int R,int k) { int mid=(l+r)>>1,suc=0x7fffffff; if (L<=l && R>=r) return Succ(now,k); if (L<=mid) suc=min(suc,GetSucc(now<<1,l,mid,L,R,k)); if (mid<R) suc=min(suc,GetSucc(now<<1|1,mid+1,r,L,R,k)); return suc; } //Solve--------------------------------------------------------------------------------------------- void solve_1(int l,int r,int k) {printf("%d ",FindRank(1,1,n,l,r,k)+1);} void solve_2(int l,int r,int k) {printf("%d ",FindKth(l,r,k));} void solve_3(int pos,int k) {ChangeK(1,1,n,pos,k);} void solve_4(int l,int r,int k) {printf("%d ",GetPrev(1,1,n,l,r,k));} void solve_5(int l,int r,int k) {printf("%d ",GetSucc(1,1,n,l,r,k));} //void debug(int now) //{ // if (!now) return; // debug(son[now][0]); // printf("%d-%d个 ",key[now],cnt[now]); // debug(son[now][1]); //} //main---------------------------------------------------------------------------------------------- int main() { // freopen("output.out","w",stdout); n=read(),m=read(); for (int i=1; i<=n; i++) a[i]=read(),maxx=max(maxx,a[i]); buildTree(1,1,n); for (int i=1; i<=m; i++) { int opt=read(),l,r,k,pos; switch (opt) { case 1: l=read(); r=read(); k=read(); solve_1(l,r,k); break; case 2: l=read(); r=read(); k=read(); solve_2(l,r,k); break; case 3: pos=read(); k=read(); solve_3(pos,k); break; case 4: l=read(); r=read(); k=read(); solve_4(l,r,k); break; case 5: l=read(); r=read(); k=read(); solve_5(l,r,k); break; } //for (int i=1;i<=17;i++) debug(root[i]),puts(""); } return 0; }
让南爷看了两个shabi错误...[好友'智商'已经掉线]...秀了一波智商下限TAT''
UPD:ShallWe大爷的 权值线段树套区间线段树 没调..留着以后学姿势
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 51000 using namespace std; int tn,Hash[N],a[N],head[N]; int n,m,totp,totin,rt; struct P{ int l,r,in; } p[4000000]; struct I{ int l,r,sz; } in[5000000]; struct Q{ int type,l,r,k; } query[N]; inline int read() { char ch=getchar();int flag=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-') flag=-1; int x=0; for(;ch>='0'&&ch<='9';x=x*10+ch-48,ch=getchar());return x*flag; } inline int DC(int x) { return lower_bound(Hash+1,Hash+1+tn,x)-Hash;} inline int DCC(int x) { int w=lower_bound(Hash+1,Hash+1+tn,x)-Hash; return w-1; } inline int DCCC(int x) { int w=upper_bound(Hash+1,Hash+1+tn,x)-Hash;} inline void Up(int x) { in[x].sz=in[in[x].l].sz+in[in[x].r].sz;} void Insert(int &x,int l,int r,int w,int delta) { if (!x) x=++totin; // cout<<x<<endl; // cout<<l<<' '<<r<<' '<<w<<endl; if (l==r){ in[x].sz+=delta; return; } int mid=(l+r)>>1; if (w<=mid) Insert(in[x].l,l,mid,w,delta); else Insert(in[x].r,mid+1,r,w,delta); Up(x); } void Add(int &x,int l,int r,int val,int whe,int delta) { if (!x) x=++totp; // cout<<l<<' '<<r<<' '<<val<<' '<<whe<<endl; Insert(p[x].in,1,n,whe,delta); if (l==r) return; int mid=(l+r)>>1; if (val<=mid) Add(p[x].l,l,mid,val,whe,delta); else Add(p[x].r,mid+1,r,val,whe,delta); } int Get_sz_in(int x,int l,int r,int L,int R) { if (!x) return 0; if (L>R) return x; if (L<=l&&r<=R) return in[x].sz; int mid=(l+r)>>1,now=0; if (L<=mid) now+=Get_sz_in(in[x].l,l,mid,L,R); if (R>mid) now+=Get_sz_in(in[x].r,mid+1,r,L,R); return now; } int Get_sz(int x,int l,int r,int L,int R,int il,int ir) { if (!x) return 0; if (L>R) return 0; // cout<<x<<' '<<l<<' '<<r<<' '<<endl; if (L<=l&&r<=R) return Get_sz_in(p[x].in,1,n,il,ir); int mid=(l+r)>>1,now=0; if (L<=mid) now+=Get_sz(p[x].l,l,mid,L,R,il,ir); if (R>mid) now+=Get_sz(p[x].r,mid+1,r,L,R,il,ir); return now; } inline int Find_rate(int l,int r,int k) { int sz=Get_sz(rt,1,tn,1,k-1,l,r); return sz+1; } inline int Find_kth(int l,int r,int k) { int L=1,R=tn,x=rt; while (L<R) { int mid=(L+R)>>1; int Left=Get_sz_in(p[p[x].l].in,1,n,l,r); if (Left>=k) R=mid,x=p[x].l; if (Left<k) k-=Left,L=mid+1,x=p[x].r; } return Hash[L]; } int main() { freopen("a.in","r",stdin); n=read(),m=read(); for (int i=1;i<=n;i++) Hash[i]=a[i]=read(); tn=n; int x,y,z,type ; for (int i=1;i<=m;i++) { type=query[i].type=read(); if (type==3) { query[i].l=read(); query[i].k=read(); Hash[++tn]=query[i].k; }else{ query[i].l=read(); query[i].r=read(); query[i].k=read(); } } // for (int i=1;i<=m;i++) // cout<<query[i].l<<' '<<query[i].r<<' '<<query[i].k<<endl; sort(Hash+1,Hash+1+tn); tn=unique(Hash+1,Hash+1+tn)-Hash; for (int i=1;i<=n;i++) Add(rt,1,tn,a[i]=DC(a[i]),i,+1); // for(int i=1;i<=n;i++) cout<<a[i]<<endl; for (int i=1;i<=m;i++) { int l=query[i].l,r=query[i].r,k=query[i].k; // cout<<query[i].type<<endl; switch (query[i].type){ case 1:{ printf("%d ",Find_rate(l,r,DC(k))); break; } case 2:{ printf("%d ",Find_kth(l,r,k)); break; } case 3:{ Add(rt,1,tn,a[l],l,-1); Add(rt,1,tn,a[l]=DC(k),l,1); break; } case 4:{ int now=DCC(k); int x=Get_sz(rt,1,tn,l,r,now,now); if (x) printf("%d ",Hash[now]); else printf("%d ",Find_kth(l,r,Find_rate(l,r,now)-1)); break; } case 5:{ int now=DCCC(k); int x=Get_sz(rt,1,tn,l,r,now,now); if (x) printf("%d ",Hash[now]); else printf("%d ",Find_kth(l,r,Find_rate(l,r,now))); break; } } } return 0; }