首页 > 代码库 > BZOJ3196 二逼平衡树
BZOJ3196 二逼平衡树
3196: Tyvj 1730 二逼平衡树
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可能为负数
所以说我可能真的不适合数据结构，泪流满面"＾"
所以说我可能真的不适合数据结构，泪流满面"＾"
我没有吃饭加浪费了一个晚自习的结果居然是一处maxv写成了maxn，终于没有写错splay居然又开错了数组有木有有木有。。。
我这时的心情是悲愤的，然而并没有什么卵用，再立flag，明天数据结构绝对1A
线段树套Splay，对于二号询问直接二分答案，Splay还是记得开哨兵
有时候函数开多一点代码反而更好写
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 template <class _T> inline void read(_T &_x) { 5 int _t; bool flag = false; 6 while ((_t = getchar()) != ‘-‘ && (_t < ‘0‘ || _t > ‘9‘)) ; 7 if (_t == ‘-‘) _t = getchar(), flag = true; _x = _t - ‘0‘; 8 while ((_t = getchar()) >= ‘0‘ && _t <= ‘9‘) _x = _x * 10 + _t - ‘0‘; 9 if (flag) _x = -_x; 10 } 11 const int maxn = 50010; 12 const int inf = 2147483647; 13 namespace S { 14 const int maxv = 4e6 + 5; 15 int *root; 16 int v[maxv], f[maxv], ch[maxv][2], sz[maxv], cnt[maxv]; 17 int st[maxv], top, tot; 18 inline int newnode(int val) { 19 if (!top) st[top++] = ++tot; 20 int cur = st[--top]; 21 v[cur] = val; 22 f[cur] = ch[cur][0] = ch[cur][1] = 0; 23 sz[cur] = cnt[cur] = 1; 24 return cur; 25 } 26 inline void update(int rt) { 27 sz[rt] = sz[ch[rt][0]] + sz[ch[rt][1]] + cnt[rt]; 28 } 29 inline void init(int &rt) { 30 rt = newnode(-inf); 31 ch[rt][1] = newnode(inf); 32 f[ch[rt][1]] = rt; 33 update(rt); 34 } 35 inline void rotate(int c) { 36 int b = f[c], a = f[b], x = ch[b][1]==c; 37 ch[b][x] = ch[c][x ^ 1], f[ch[b][x]] = b; 38 ch[c][x ^ 1] = b, f[b] = c; 39 if (a) ch[a][ch[a][1]==b] = c; else *root = c; 40 f[c] = a; update(b); 41 } 42 inline int splay(int c, int a = 0) { 43 for (int b; (b = f[c]) != a; rotate(c)) if (f[b] != a) 44 rotate((ch[f[b]][1]==b)==(ch[b][1]==c)?b:c); 45 update(c); return c; 46 } 47 inline int query_pre(int rt, int val) { 48 int ret = 0, ori = f[rt]; 49 do { 50 if (v[rt] < val) ret = rt; 51 rt = ch[rt][v[rt] < val]; 52 } while (rt); 53 return splay(ret, ori); 54 } 55 inline int query_suc(int rt, int val) { 56 int ret = 0, ori = f[rt]; 57 do { 58 if (v[rt] > val) ret = rt; 59 rt = ch[rt][v[rt] <= val]; 60 } while (rt); 61 return splay(ret, ori); 62 } 63 inline int pre(int rt, int a = 0) { 64 rt = ch[rt][0]; 65 while (ch[rt][1]) rt = ch[rt][1]; 66 return splay(rt, a); 67 } 68 inline int suc(int rt, int a = 0) { 69 rt = ch[rt][1]; 70 while (ch[rt][0]) rt = ch[rt][0]; 71 return splay(rt, a); 72 } 73 inline void remove(int rt, int val) { 74 int x = query_pre(rt, val); 75 int y = suc(x, x); 76 if (cnt[y] > 1) --cnt[y]; 77 else { 78 int z = suc(y, x); 79 st[top++] = y, ch[z][0] = 0, y = z; 80 } 81 update(y), update(x); 82 } 83 inline void insert(int &rt, int val) { 84 root = &rt; 85 int x = query_pre(rt, val); 86 int y = suc(x, x); 87 if (v[y] == val) ++cnt[y]; 88 else { 89 int z = ch[y][0] = newnode(val); 90 f[z] = y; 91 } 92 update(y), update(x); 93 } 94 inline void change(int &rt, int ori, int to) { 95 root = &rt; 96 remove(rt, ori); 97 insert(rt, to); 98 } 99 inline int Query_cnt(int &rt, int val) {100 root = &rt;101 query_suc(rt, val);102 return sz[ch[rt][0]] - 1;103 }104 inline int Query_suc(int &rt, int val) {105 root = &rt;106 return v[query_suc(rt, val)];107 }108 inline int Query_pre(int &rt, int val) {109 root = &rt;110 return v[query_pre(rt, val)];111 }112 inline int Query_rk(int &rt, int val) {113 root = &rt;114 int x = query_pre(rt, val);115 return sz[ch[x][0]] + cnt[x] - 1;116 }117 }118 int n, m, a[maxn], root[maxn * 20];119 #define lson rt << 1, l, mid120 #define rson rt << 1 | 1, mid + 1, r121 void build(int rt, int l, int r) {122 S::init(root[rt]);123 for (int i = l; i <= r; ++i)124 S::insert(root[rt], a[i]);125 if (l == r) return ;126 int mid = (l + r) >> 1;127 build(lson), build(rson);128 }129 int query_cnt(int rt, int l, int r, int L, int R, int val) { //cnt of less or equal130 if (L <= l && r <= R) return S::Query_cnt(root[rt], val);131 int mid = (l + r) >> 1, ret = 0;132 if (L <= mid) ret += query_cnt(lson, L, R, val);133 if (mid < R) ret += query_cnt(rson, L, R, val);134 return ret;135 }136 int query_pre(int rt, int l, int r, int L, int R, int val) { //less than val137 if (L <= l && r <= R) return S::Query_pre(root[rt], val);138 int mid = (l + r) >> 1, ret = -inf;139 if (L <= mid) ret = max(ret, query_pre(lson, L, R, val));140 if (mid < R) ret = max(ret, query_pre(rson, L, R, val));141 return ret;142 }143 int query_suc(int rt, int l, int r, int L, int R, int val) { //more than val144 if (L <= l && r <= R) return S::Query_suc(root[rt], val);145 int mid = (l + r) >> 1, ret = inf;146 if (L <= mid) ret = min(ret, query_suc(lson, L, R, val));147 if (mid < R) ret = min(ret, query_suc(rson, L, R, val));148 return ret;149 }150 int query_precnt(int rt, int l, int r, int L, int R, int val) {151 if (L <= l && r <= R) return S::Query_rk(root[rt], val);152 int mid = (l + r) >> 1, ret = 0;153 if (L <= mid) ret += query_precnt(lson, L, R, val);154 if (mid < R) ret += query_precnt(rson, L, R, val);155 return ret;156 }157 void update(int rt, int l, int r, int pos, int val) { // update pos to val158 S::change(root[rt], a[pos], val);159 if (l == r) return ;160 int mid = (l + r) >> 1;161 if (pos <= mid) update(lson, pos, val);162 else update(rson, pos, val);163 }164 inline int Query_kth(int L, int R, int k) {165 int l = 0, r = 1e8, mid;166 while (l < r) {167 mid = (l + r) >> 1;168 if (query_cnt(1, 1, n, L, R, mid) >= k) r = mid;169 else l = mid + 1;170 }171 return l;172 }173 inline int Query_pre(int L, int R, int val) {174 return query_pre(1, 1, n, L, R, val);175 }176 inline int Query_suc(int L, int R, int val) {177 return query_suc(1, 1, n, L, R, val);178 }179 inline int Query_rk(int L, int R, int val) {180 return query_precnt(1, 1, n, L, R, val) + 1;181 }182 inline void Update(int pos, int val) {183 update(1, 1, n, pos, val);184 a[pos] = val;185 }186 int main() {187 //freopen("3196.in", "r", stdin);188 //freopen("3196.out", "w", stdout);189 read(n), read(m);190 for (int i = 1; i <= n; ++i) read(a[i]);191 build(1, 1, n);192 for (int i = 1, op, x, y, z; i <= m; ++i) {193 read(op);194 switch (op) {195 case 1:196 read(x), read(y), read(z);197 printf("%d\n", Query_rk(x, y, z));198 break;199 case 2:200 read(x), read(y), read(z);201 printf("%d\n", Query_kth(x, y, z));202 break;203 case 3:204 read(x), read(y);205 Update(x, y);206 break;207 case 4:208 read(x), read(y), read(z);209 printf("%d\n", Query_pre(x, y, z));210 break;211 case 5:212 read(x), read(y), read(z);213 printf("%d\n", Query_suc(x, y, z));214 break;215 }216 }217 return 0;218 }
BZOJ3196 二逼平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。