Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1363 Solved: 579 [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
Sample Output2
4
3
4
9
HINT1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数
【题解】
线段树套一个平衡树。 对于线段树的每个节点所代表的区间维护一个平衡树(包含了这个区间里面的所有元素); 用的是SBT(这可能是这份题解唯一的卖点了,我看网上其他人用的都是treap,200+行左右,然而我用了300+行)。 找第k小的数的时候用到了二分答案。 修改操作可以看成是在平衡树里面删掉原来的值。然后再把新的值加入到平衡树中。 这道题的rank是这样的 1 2 3 3 3 5 6 7 8 9 3的rank是3 但是如果查rank4也是3,rank5 也是3,rank3也是3 删除操作有点复杂,因为左右儿子都有的情况需要找个节点来替代,而且这个节点的重复次数也需要改变(同一个数字记录在同一个节点,用”重复”域来表示这个数字重复了几次; 还有,因为同一数字压缩在了同一个节点。所以左旋、右旋代码的size域的修改有所改变/**************************************************************Problem: 3196User: chengchunyangLanguage: C++Result: AcceptedTime:7420 msMemory:65572 kb****************************************************************/#includeconst int MAXN = 51000;const int INF = 1e8 + 10;//记住要乘16倍就好。//有MAX*4个是存放树的根节点//MAX*4*15个是这些树的儿子节点int root[MAXN * 4], l[MAXN * 4 * 16], r[MAXN * 4 * 16], key[MAXN * 4 * 16], size[MAXN * 4 * 16], cnt = 0;int a[MAXN], n, m, rank = 0, cf[MAXN * 4 * 16];//cf代表这个数字重复出现了几次int qianqu, houji;int min(int a, int b){ return a > b ? b : a;}int max(int a, int b){ return a > b ? a : b;}void r_ro(int &t)//右旋代码{ int k = l[t]; l[t] = r[k]; r[k] = t; size[k] = size[t]; size[t] = size[l[t]] + size[r[t]] + cf[t];//最后加上的不是1而是cf[t]了。 t = k;}void l_ro(int &t)//左旋{ int k = r[t]; r[t] = l[k]; l[k] = t; size[k] = size[t]; size[t] = size[l[t]] + size[r[t]] + cf[t]; t = k;}void maintain(int &t, bool flag)//sbt的修复函数{ if (flag) { if (size[l[l[t]]] > size[r[t]]) r_ro(t); else if (size[r[l[t]]] > size[r[t]]) l_ro(l[t]), r_ro(t); else return; } else { if (size[r[r[t]]] > size[l[t]]) l_ro(t); else if (size[l[r[t]]] > size[l[t]]) r_ro(r[t]), l_ro(t); else return; } maintain(l[t], true); maintain(r[t], false); maintain(t, true); maintain(t, false);}void insert(int &t, int x)//插入过程{ if (!t) { t = ++cnt; size[t] = cf[t] = 1; l[t] = r[t] = 0; key[t] = x; } else { size[t]++; if (x == key[t]) cf[t]++; else if (x < key[t]) insert(l[t], x); else insert(r[t], x); if (x != key[t]) maintain(t, x < key[t]); }}void ask_rank(int t, int x)//获取排名,获取的是比它小的数字的个数{ if (!t) return; if (x == key[t])//等于就即加上左子树的大小 rank += size[l[t]]; else if (x < key[t]) ask_rank(l[t], x); else if (x > key[t])//大于 { rank += size[l[t]] + cf[t];//整个左子树和这个节点都行 ask_rank(r[t], x); }}void get_rank(int rt, int begin, int end, int l, int r, int x){ //线段树,获取这个l,r区间所在的平衡树 if (begin == l && end == r) { ask_rank(root[rt], x); return; } int m = (begin + end) >> 1; if (r <= m) get_rank(rt << 1, begin, m, l, r, x); else if (m < l) get_rank(rt << 1 | 1, m + 1, end, l, r, x); else { get_rank(rt << 1, begin, m, l, m, x); get_rank(rt << 1 | 1, m + 1, end, m + 1, r, x); }}void build(int rt, int begin, int end, int pos, int x){ //建线段树,并维护平衡树 insert(root[rt], x); if (begin == end) return; int m = (begin + end) >> 1; if (pos <= m) build(rt << 1, begin, m, pos, x); else build(rt << 1 | 1, m + 1, end, pos, x);}void de_lete(int &t, int x){ //删掉x这个元素 if (!t) return; size[t]--; if (key[t] == x) { if (cf[t] > 1) cf[t]--; else { cf[t] = 0; bool flag1 = (l[t]>0), flag2 = (r[t]>0); if (!flag1 && !flag2) t = 0; else if (!flag1 && flag2) t = r[t]; else if (flag1 && !flag2) t = l[t]; else { int temp = r[t]; while (l[temp]) temp = l[temp];//这里要用一个节点替代它 int dd = cf[temp] - 1; temp = r[t]; size[temp] -= dd;//相应的size域都要发生变化 while (l[temp]) { temp = l[temp]; size[temp] -= dd; } key[t] = key[temp];//替代 cf[t] = cf[temp];//那个节点的cf域变成1 cf[temp] = 1; de_lete(r[t], key[temp]);//下次就会删掉了。 } } } else if (x < key[t]) de_lete(l[t], x); else de_lete(r[t], x);}void change(int rt, int begin, int end, int pos, int x){ //更改值实际上就是在平衡树中删掉一个元素,然后再添加进去 de_lete(root[rt], a[pos]); insert(root[rt], x); if (begin == end) return; int m = (begin + end) >> 1; if (pos <= m) change(rt << 1, begin, m, pos, x); else change(rt << 1 | 1, m + 1, end, pos, x);}void ask_before(int t, int x){ //询问前趋是啥 if (!t) return; if (key[t] < x) { qianqu = max(qianqu, key[t]); ask_before(r[t], x); } else if (x <= key[t]) ask_before(l[t], x);}void get_before(int rt, int begin, int end, int l, int r, int k){ //获取这个区间所在的平衡树 if (begin == l && end == r) { ask_before(root[rt], k); return; } int m = (begin + end) >> 1; if (r <= m) get_before(rt << 1, begin, m, l, r, k); else if (m < l) get_before(rt << 1 | 1, m + 1, end, l, r, k); else { get_before(rt << 1, begin, m, l, m, k); get_before(rt << 1 | 1, m + 1, end, m + 1, r, k); }}void ask_houji(int t, int x){ //询问后继 if (!t) return; if (x < key[t]) { houji = min(houji, key[t]); ask_houji(l[t], x); } else if (x >= key[t]) ask_houji(r[t], x);}void get_houji(int rt, int begin, int end, int l, int r, int k){ //获取这个区间所在的平衡树 if (begin == l && end == r) { ask_houji(root[rt], k); return; } int m = (begin + end) >> 1; if (r <= m) get_houji(rt << 1, begin, m, l, r, k); else if (m < l) get_houji(rt << 1 | 1, m + 1, end, l, r, k); else { get_houji(rt << 1, begin, m, l, m, k); get_houji(rt << 1 | 1, m + 1, end, m + 1, r, k); }}int main(){ //freopen("F:\\rush.txt", "r", stdin); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); build(1, 1, n, i, a[i]); } for (int i = 1; i <= m; i++) { int opt; scanf("%d", &opt); if (opt == 1) { int l, r, k; scanf("%d%d%d", &l, &r, &k); rank = 1; get_rank(1, 1, n, l, r, k); printf("%d\n", rank); } else if (opt == 2) { int l, r, k; scanf("%d%d%d", &l, &r, &k); int le = 0, ri = INF, num;//询问第k小数实际上是二分一个数字,然后判断它的排名 while (le <= ri)//不断调整 { int m = (le + ri) >> 1; rank = 1;//我们找的是小于这个数的个数.所以一开始加上1就是这个数的排名了。 get_rank(1, 1, n, l, r, m); if (rank <= k)//小于等于k就记录这个m为答案。 { //最后记录的是满足排名小于等于k的最大的一个数字. le = m + 1; num = m; } else if (rank > k) ri = m - 1; } printf("%d\n", num); } else if (opt == 3) { int pos, x; scanf("%d%d", &pos, &x); change(1, 1, n, pos, x); a[pos] = x; } else if (opt == 4) { int l, r, k; scanf("%d%d%d", &l, &r, &k); qianqu = 0; get_before(1, 1, n, l, r, k); printf("%d\n", qianqu); } else if (opt == 5) { int l, r, k; scanf("%d%d%d", &l, &r, &k); houji = INF; get_houji(1, 1, n, l, r, k); printf("%d\n", houji); } } return 0;}