BZOJ3196: Tyvj 1730 二逼平衡树

命題

需要一种数据结构,来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)


For the operation 1, 3, 4, 5. Build a segment tree with a balanced tree on every node. These four operations can be done in each balanced tree. Merge the answer on each one at last.

For the operation 2. We use binary search in $[0,10^8]$ to locate the answer. This operation will be turned into operation 1.

 
#include <cstdio> #include <algorithm> #include <climits> using namespace std; const int N = 50000 + 5; const int inf = 100000000; int n, m; class Segtree { public: class Node { public: int x; int siz; int rad; Node *ch[2]; Node(int x = 0) : x(x) { ch[0] = ch[1] = NULL; siz = 1; rad = rand(); } int cmp(int vx) const { if (x == vx) return -1; return vx < x ? 0 : 1; } void maintain() { siz = 1; if (ch[0]) siz += ch[0]->siz; if (ch[1]) siz += ch[1]->siz; } }; typedef Node *Treap; void rotate(Node *&o, int d) { Node *k = o->ch[d ^ 1]; o->ch[d ^ 1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(Node *&o, int x) { if (o == NULL) { o = new Node(x); } else { int d = x < o->x ? 0 : 1; insert(o->ch[d], x); if (o->ch[d]->rad > o->rad) rotate(o, d ^ 1); } o->maintain(); } Treap tr[8 * N]; void build(int l, int r, int id, int x, int p) { insert(tr[p], x); if (l == r) return; int mid = (l + r) / 2; if (id <= mid) build(l, mid, id, x, p << 1); else build(mid + 1, r, id, x, p << 1 | 1); } void remove(Node *&o, int x) { int d = o->cmp(x); if (d == -1) { Node *u = o; if (o->ch[0] != NULL && o->ch[1] != NULL) { int d2 = o->ch[0]->rad > o->ch[1]->rad ? 1 : 0; rotate(o, d2); remove(o->ch[d2], x); } else { if (o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0]; delete u; } } else remove(o->ch[d], x); if (o != NULL) o->maintain(); } void update(int l, int r, int id, int pre, int x, int p) { remove(tr[p], pre); insert(tr[p], x); if (l == r) return; int mid = (l + r) / 2; if (id <= mid) update(l, mid, id, pre, x, p << 1); else update(mid + 1, r, id, pre, x, p << 1 | 1); } int rank(Node *p, int k) { if (p == NULL) return 0; int cnt = 1; if (k > p->x) { if (p->ch[0]) cnt += p->ch[0]->siz; return cnt + rank(p->ch[1], k); } else return rank(p->ch[0], k); } int queryRank(int l, int r, int L, int R, int x, int p) { if (L <= l && r <= R) return rank(tr[p], x); int mid = (l + r) / 2; int cnt = 0; if (L <= mid) cnt += queryRank(l, mid, L, R, x, p << 1); if (R > mid) cnt += queryRank(mid + 1, r, L, R, x, p << 1 | 1); return cnt; } int queryKth(int l, int r, int k) { int L = 0, R = inf, mid; while (L < R) { mid = (L + R) / 2; int rk = queryRank(1, n, l, r, mid, 1); // printf("\tmid = %d less = %d\n", mid, rk); if (rk + 1 <= k) L = mid + 1; else R = mid; } return R - 1; } Node *findPrecursor(Node *p, Node *q, int k) { if (p == NULL) return q; if (k - 1 < p->x) return findPrecursor(p->ch[0], q, k); return findPrecursor(p->ch[1], p, k); } Node *findSuccessor(Node *p, Node *q, int k) { // printf("find [%d, %d, %d]\n", p ? p->x : -1, q ? q->x : -1, k); if (p == NULL) return q; if (k < p->x) return findSuccessor(p->ch[0], p, k); return findSuccessor(p->ch[1], q, k); } int getPrecursor(int l, int r, int L, int R, int x, int p) { Node *t; if (l > R || r < L) return 0; if (L <= l && r <= R) return (t = findPrecursor(tr[p], NULL, x)) == NULL ? 0 : t->x; int mid = (l + r) / 2; return max(getPrecursor(l, mid, L, R, x, p << 1), getPrecursor(mid + 1, r, L, R, x, p << 1 | 1)); } int getSuccessor(int l, int r, int L, int R, int x, int p) { // printf("at [%d, %d] [%d, %d] %d\n", l, r, L, R, x); Node *t; if (l > R || r < L) return inf; if (L <= l && r <= R) return (t = findSuccessor(tr[p], NULL, x)) == NULL ? inf : t->x; int mid = (l + r) / 2; return min(getSuccessor(l, mid, L, R, x, p << 1), getSuccessor(mid + 1, r, L, R, x, p << 1 | 1)); } void print(Node *p) { if (p->ch[0]) print(p->ch[0]); printf("%d ", p->x); if (p->ch[1]) print(p->ch[1]); } }; Segtree A; int a[N]; int main() { srand(260817); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) A.build(1, n, i, a[i], 1); for (int i = 1; i <= m; i++) { int op, l, r, k; scanf("%d", &op); if (op == 1) scanf("%d%d%d", &l, &r, &k), printf("%d\n", A.queryRank(1, n, l, r, k, 1) + 1); if (op == 2) scanf("%d%d%d", &l, &r, &k), printf("%d\n", A.queryKth(l, r, k)); if (op == 3) scanf("%d%d", &l, &k), A.update(1, n, l, a[l], k, 1), a[l] = k; if (op == 4) scanf("%d%d%d", &l, &r, &k), printf("%d\n", A.getPrecursor(1, n, l, r, k, 1)); if (op == 5) scanf("%d%d%d", &l, &r, &k), printf("%d\n", A.getSuccessor(1, n, l, r, k, 1)); } return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注