题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名2.查询区间内排名为k的值3.修改某一位值上的数值4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)5.查询k在区间内的后继(后继定义为大于x，且最小的数)输入
第一行两个数 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的后继输出
对于操作1,2,4,5各输出一行，表示查询结果
样例输入
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
样例输出
2 4 3 4 9
题解
树套树，外层线段树内层Treap
对于外层线段树的每个节点，在此之上建立一棵Treap。
这样用外层线段树维护区间，内层Treap维护排名，能够轻松处理出询问1、3、4、5。
具体地，1操作在线段树中不断查找区间，在线段树节点对应的Treap中查找有多少个比k小的，类似于普通线段树的区间查询。4、5操作同理。
3操作在线段树中不断查找区间，在线段树节点对应的Treap中删除原数，添加新数，类似于普通线段树的单点修改。
然而仅仅是这样并不能处理出2操作。
考虑到查某排名的数很不容易，但查某数的排名比较简单（操作1），于是我们可以二分答案，并用操作1的方法判断即可。
1、3、4、5操作时间复杂度O(log^2n)，2操作时间复杂度O(log^3n)。
常数已经优化到比较小了，亲测在某些卡时间的oj上可以过。
#include#include #include #define N 200010#define M 4000010#define inf 0x7fffffff#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;int n , v[N] , root[N] , w[M] , cnt[M] , si[M] , ls[M] , rs[M] , rnd[M] , tot;void pushup(int k){ si[k] = si[ls[k]] + si[rs[k]] + cnt[k];}void zig(int &k){ int t = ls[k]; ls[k] = rs[t] , rs[t] = k , si[t] = si[k] , pushup(k) , k = t;}void zag(int &k){ int t = rs[k]; rs[k] = ls[t] , ls[t] = k , si[t] = si[k] , pushup(k) , k = t;}void ins(int &k , int a){ if(!k) { k = ++tot , w[k] = a , cnt[k] = si[k] = 1 , rnd[k] = rand(); return; } si[k] ++ ; if(a == w[k]) cnt[k] ++ ; else if(a < w[k]) { ins(ls[k] , a); if(rnd[ls[k]] < rnd[k]) zig(k); } else { ins(rs[k] , a); if(rnd[rs[k]] < rnd[k]) zag(k); }}void del(int &k , int a){ if(a == w[k]) { if(cnt[k] > 1) cnt[k] -- , si[k] -- ; else if(!ls[k] || !rs[k]) k = ls[k] + rs[k]; else if(rnd[ls[k]] < rnd[rs[k]]) zig(k) , del(k , a); else zag(k) , del(k , a); } else if(a < w[k]) del(ls[k] , a) , si[k] -- ; else del(rs[k] , a) , si[k] -- ;}int getless(int k , int a){ if(!k) return 0; if(a <= w[k]) return getless(ls[k] , a); else return getless(rs[k] , a) + si[ls[k]] + cnt[k];}int getpro(int k , int a){ if(!k) return 0; if(a <= w[k]) return getpro(ls[k] , a); else return max(w[k] , getpro(rs[k] , a));}int getsub(int k , int a){ if(!k) return inf; if(a >= w[k]) return getsub(rs[k] , a); else return min(w[k] , getsub(ls[k] , a));}void build(int l , int r , int x){ int i , mid = (l + r) >> 1; for(i = l ; i <= r ; i ++ ) ins(root[x] , v[i]); if(l == r) return; build(lson) , build(rson);}void update(int p , int a , int l , int r , int x){ del(root[x] , v[p]) , ins(root[x] , a); if(l == r) return; int mid = (l + r) >> 1; if(p <= mid) update(p , a , lson); else update(p , a , rson);}int queryless(int b , int e , int a , int l , int r , int x){ if(b <= l && r <= e) return getless(root[x] , a); int mid = (l + r) >> 1 , ans = 0; if(b <= mid) ans += queryless(b , e , a , lson); if(e > mid) ans += queryless(b , e , a , rson); return ans;}int querypro(int b , int e , int a , int l , int r , int x){ if(b <= l && r <= e) return getpro(root[x] , a); int mid = (l + r) >> 1 , ans = 0; if(b <= mid) ans = max(ans , querypro(b , e , a , lson)); if(e > mid) ans = max(ans , querypro(b , e , a , rson)); return ans;}int querysub(int b , int e , int a , int l , int r , int x){ if(b <= l && r <= e) return getsub(root[x] , a); int mid = (l + r) >> 1 , ans = inf; if(b <= mid) ans = min(ans , querysub(b , e , a , lson)); if(e > mid) ans = min(ans , querysub(b , e , a , rson)); return ans;}int solvenum(int b , int e , int a){ int l = querysub(b , e , -1 , 1 , n , 1) , r = querypro(b , e , inf , 1 , n , 1) , mid , ans = 0; while(l <= r) { mid = (l + r) >> 1; if(queryless(b , e , mid , 1 , n , 1) + 1 <= a) ans = mid , l = mid + 1; else r = mid - 1; } return ans;}int main(){ int m , i , opt , x , y , z; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i]); build(1 , n , 1); while(m -- ) { scanf("%d%d%d" , &opt , &x , &y); if(opt != 3) scanf("%d" , &z); switch(opt) { case 1: printf("%d\n" , queryless(x , y , z , 1 , n , 1) + 1); break; case 2: printf("%d\n" , solvenum(x , y , z)); break; case 3: update(x , y , 1 , n , 1) , v[x] = y; break; case 4: printf("%d\n" , querypro(x , y , z , 1 , n , 1)); break; default: printf("%d\n" , querysub(x , y , z , 1 , n , 1)); } } return 0;}