题解 P3369 【【模板】普通平衡树】

olinr

2018-08-03 16:14:50

Solution

# ~~蒟蒻第一篇题解~~ ## 看到有位%%巨佬%%居然写了红黑树(看不懂) ## 不过这题可以用线段树k掉 ---------------------实现----------------------- ### 我们把线段树开成一个桶 ### 离线操作 ### 每个节点所代表的区间为区间内数的个数 ### 这样写不仅码量减少了,运行速度也快了不少 --- 1.插入 从根节点到叶子节点,权值+1; 2.删除 同上,节点权值-1; 因此,以上操作可以写成一个函数 inline void add_or_del(int o,int l,int r,int k,int pos) { st[o]+=pos;//加或减 if(l==r) return; //到叶子节点 int mid=(l+r)>>1; if(k<=mid) add_or_del(ls,l,mid,k,pos); //分别向左右儿子递归 else add_or_del(rs,mid+1,r,k,pos); } 非常简单,而且开始都不用建树(桶为空) 3.查询 x 数的排名: 每次把x与当前区间中点mid比较 如果小于等于mid,说明在左区间,向左儿子寻找 如果大于mid,说明在右区间 这时,它的排名要加上左子树的大小(它比整个左子树的数都大) 边界,当l==r时(到了叶子),那么return 1;(在[l,r]的区间只有自己,排名第一) QAQ代码 inline int x_rank_n(int o,int l,int r,int k) { if(l==r) return 1; int mid=(l+r)>>1; if(k<=mid) return x_rank_n(ls,l,mid,k); else return st[ls]+x_rank_n(rs,mid+1,r,k); } 4.查询排名为x的数 原理同上,注意在向右儿子找的时候要减去左儿子大小 5.x的前驱 等于排在 x的排名减一 位置的数 6.x的后继 等于排在 x+1的排名 位置的数 ### 全部代码如下 ```cpp #include<cstdio> #include<iostream> #include<cctype> #include<algorithm> using namespace std; #define int long long #define ls (o<<1) #define rs (ls|1) int b[100500]; int a[100500]; int val[100500]; int st[405000]; int n; int tot; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) put(x/10); putchar(x%10+'0'); } inline void add_or_del(int o,int l,int r,int k,int pos) { st[o]+=pos; if(l==r) return; int mid=(l+r)>>1; if(k<=mid) add_or_del(ls,l,mid,k,pos); else add_or_del(rs,mid+1,r,k,pos); } inline int x_rank_n(int o,int l,int r,int k) { if(l==r) return 1; int mid=(l+r)>>1; if(k<=mid) return x_rank_n(ls,l,mid,k); else return st[ls]+x_rank_n(rs,mid+1,r,k); } inline int n_rank_x(int o,int l,int r,int k) { if(l==r) return l; int mid=(l+r)>>1; if(st[ls]>=k) return n_rank_x(ls,l,mid,k); else return n_rank_x(rs,mid+1,r,k-st[ls]); } signed main() { n=read(); for(int i=1;i<=n;i++) { val[i]=read(); a[i]=read(); if(val[i]!=4) b[++tot]=a[i]; } sort(b+1,b+tot+1); for(int i=1;i<=n;i++) { if(val[i]!=4) a[i]=lower_bound(b+1,b+tot+1,a[i])-b; } for(int i=1;i<=n;i++) { switch(val[i]) { case 1: add_or_del(1,1,tot,a[i],1);break; case 2: add_or_del(1,1,tot,a[i],-1);break; case 3: put(x_rank_n(1,1,tot,a[i]));putchar('\n');break; case 4: put(b[n_rank_x(1,1,tot,a[i])]);putchar('\n');break; case 5: put(b[n_rank_x(1,1,tot,x_rank_n(1,1,tot,a[i])-1)]);putchar('\n');break; default: put(b[n_rank_x(1,1,tot,x_rank_n(1,1,tot,a[i]+1))]);putchar('\n'); } } return 0; } ``` ### 跑了388ms