1370 字
7 分钟
BZOJ 1901 [Zju2112] Dynamic Rankings
Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1 ],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改 变后的a继续回答上面的问题。
Input
第一行一个数字N，代表测试组数 对于每组数据第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。 C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t
Output
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Sample Input
1
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
题解
简单的来说就是待修改的区间k小值
我们用让线段树外面套一层树状数组就可以修改了
#include <iostream>#include <cstdio>#include <algorithm>#include <vector>#include <cstring>using namespace std;const int N = 1000000000;#define lowbit(_) ((_) & (-_))struct Seg_Node{ Seg_Node *ch[2]; int sum, l, r; Seg_Node(int L, int R) { sum = 0, l = L, r = R; ch[1] = ch[0] = NULL; }#define sum(_) ((_) ? (_)->sum : 0) void Pushup() { sum = sum(ch[0]) + sum(ch[1]); }} * root[50005];int a[50005];int n;void Insert(Seg_Node *rt, int num){ if (rt->l == rt->r) { rt->sum++; return; } int m = rt->l + rt->r >> 1; if (num <= m) { if (!rt->ch[0]) rt->ch[0] = new Seg_Node(rt->l, m); Insert(rt->ch[0], num); } else { if (!rt->ch[1]) rt->ch[1] = new Seg_Node(m + 1, rt->r); Insert(rt->ch[1], num); } rt->Pushup();}void Insert(int x, int num){ for (int i = x; i <= n; i += lowbit(i)) { if (root[i] == NULL) root[i] = new Seg_Node(0, N); Insert(root[i], num); }}void Delete(Seg_Node *&rt, int num){ if (rt->l == rt->r) { rt->sum--; if (!rt->sum) delete rt, rt = NULL; return; } int m = rt->l + rt->r >> 1; if (num <= m) Delete(rt->ch[0], num); else Delete(rt->ch[1], num); rt->Pushup(); if (!rt->sum) delete rt, rt = NULL;}void Delete(int x, int num){ for (int i = x; i <= n; i += lowbit(i)) { Delete(root[i], num); }}vector<Seg_Node *> Get(int x){ vector<Seg_Node *> ans; for (int i = x; i > 0; i -= lowbit(i)) { ans.push_back(root[i]); } return ans;}vector<Seg_Node *> Get_ch(vector<Seg_Node *> x, int op){ for (int i=0;i<x.size();i++) if (x[i]) x[i] = x[i]->ch[op]; return x;}int Query(vector<Seg_Node *> list1, vector<Seg_Node *> list2, int l, int r, int k){ if (l == r) return l; int ans = 0; for (int i=0;i<list2.size();i++) if (list2[i]) ans += sum(list2[i]->ch[0]); for (int i=0;i<list1.size();i++) if (list1[i]) ans -= sum(list1[i]->ch[0]); int m = l + r >> 1; if (ans >= k) return Query(Get_ch(list1, 0), Get_ch(list2, 0), l, m, k); else return Query(Get_ch(list1, 1), Get_ch(list2, 1), m + 1, r, k - ans);}void DFS(Seg_Node *&rt){ if (rt) { DFS(rt->ch[0]); DFS(rt->ch[1]); delete rt; rt=NULL; }}void remove(){ for (int i = 1; i <= n; i++) { DFS(root[i]); }}int main(int argc, char const *argv[]){ //freopen("dynrank.in","r",stdin); //freopen("dynrank.out","w",stdout); //int T; //scanf("%d", &T); //while (T--) //{ int m; scanf("%d%d", &n, &m); //memset(a,0,sizeof(a)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); Insert(i, a[i]); } //sort(a + 1, a + n + 1); char op[3]; int p, b, c; for (int i = 1; i <= m; i++) { scanf("%s", op); if (op[0] == 'Q') { scanf("%d%d%d", &p, &b, &c); printf("%d\n", Query(Get(p - 1), Get(b), 0, N, c)); } else { scanf("%d%d", &p, &b); Delete(p, a[p]); Insert(p, b); a[p] = b; } } remove(); // } return 0;}树套树
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[50005], n;class Treap{ class Node { public: int size, v, key; Node *ch[2]; Node(int x) { key = rand(); v = x; size = 1; ch[0] = ch[1] = NULL; }#define size(_) ((_) ? (_)->size : 0) void Pushup() { size = size(ch[0]) + size(ch[1]) + 1; } } * root; Node *Merge(Node *A, Node *B) { if (!A) return B; if (!B) return A; if (A->key > B->key) { A->ch[1] = Merge(A->ch[1], B); A->Pushup(); return A; } else { B->ch[0] = Merge(A, B->ch[0]); B->Pushup(); return B; } } typedef pair<Node *, Node *> DNode; DNode Split(Node *rt, int k) { if (!rt) return DNode(NULL, NULL); DNode o; if (size(rt->ch[0]) >= k) { o = Split(rt->ch[0], k); rt->ch[0] = o.second; rt->Pushup(); o.second = rt; } else { o = Split(rt->ch[1], k - size(rt->ch[0]) - 1); rt->ch[1] = o.first; rt->Pushup(); o.first = rt; } return o; } public: Treap() { root = NULL; } int kth(int k) { DNode x = Split(root, k - 1); DNode y = Split(x.second, 1); Node *ans = y.first; root = Merge(x.first, Merge(y.first, y.second)); return ans->v; } int rank(int x) { return rank(root, x); } int rank(Node *rt, int x) { if (!rt) return 0; return x <= rt->v ? rank(rt->ch[0], x) : rank(rt->ch[1], x) + size(rt->ch[0]) + 1; } void Insert(int x) { int k = rank(root, x); DNode y = Split(root, k); Node *n = new Node(x); root = Merge(Merge(y.first, n), y.second); } void remove(int x) { int k = rank(root, x); DNode a = Split(root, k); DNode b = Split(a.second, 1); root = Merge(a.first, b.second); }} root[50005 << 2];#define lch l, m, rt << 1#define rch m + 1, r, rt << 1 | 1void build(int l, int r, int rt){ for (int i = l; i <= r; i++) root[rt].Insert(a[i]);}void buildtree(int l, int r, int rt){ build(l, r, rt); if (l == r) return; int m = l + r >> 1; buildtree(lch); buildtree(rch);}void updata(int k, int x, int y, int l, int r, int rt){ root[rt].remove(y); root[rt].Insert(x); if (l == r) return; int m = l + r >> 1; if (k <= m) updata(k, x, y, lch); else updata(k, x, y, rch);}int rank(int L, int R, int x, int l, int r, int rt){ if (L <= l && R >= r) return root[rt].rank(x); int m = l + r >> 1; if (R <= m) return rank(L, R, x, lch); if (L > m) return rank(L, R, x, rch); return rank(L, R, x, lch) + rank(L, R, x, rch);}int kth(int L, int R, int k){ int l = -1e10, r = 1e10; while (l <= r) { int m = l + r >> 1; int num = rank(L, R, m, 1, n, 1) + 1; if (num <= k) l = m + 1; else r = m - 1; } return r;}int main(){ //freopen("dynrank.in", "r", stdin); //freopen("dynrank.out", "w", stdout); //int T; //scanf("%d", &T); //while (T--) //{ // memset(root,0,sizeof(root)); int m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); buildtree(1, n, 1); char s[5]; int i, j, k, t; while (m--) { scanf("%s", s); if (s[0] == 'Q') { scanf("%d%d%d", &i, &j, &k); printf("%d\n", kth(i, j, k)); } else { scanf("%d%d", &i, &t); updata(i, t, a[i], 1, n, 1); a[i] = t; } } //}} BZOJ 1901 [Zju2112] Dynamic Rankings
https://www.nekomio.com/posts/55/