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继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数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

Sample Output

HINT

20%的数据中，m,n≤100;

40%的数据中，m,n≤1000;

100%的数据中，m,n≤10000。

Solution

还记得第一次看到这题目是在2016元旦左右，当时还愣了一下QAQ，感觉是平衡树，想了想又感觉不是，Urimoo神犇给予了蒟蒻指点之后才想出来用树状数组维护主席树QAQ。Orz Urimoo

因为每颗线段树代表了原来的序列中的某一个前缀，因此朴素的修改操作需要改N颗线段树。关于这个，大家可以参阅我的文章：Query on a tree III。但是这种维护方式复杂度不能接受。于是我们考虑维护前缀。于是想到了用树状数组维护前缀。修改、查询按照树状数组的方法操作即可在log N的时间内完成。于是树状数组log N+主席树log N+M次操作，总起来是Mlog^2N的算法。

然后注意一些细节什么的，比如如何离散化啊什么的。（蒟蒻离散化用的平衡树QAQ。。。一开始写rotate的时候“c[z][1]==y”打成了“c[z][y]==1” RE了3次 QAQ。。。。）

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int n, m;
const int maxn = 10005;
const int size = 20105;
int tot = 0, siz[size * 250], lc[size * 250], rc[size * 250], root[maxn], A[maxn];
inline int lowbit(int x) { return x & (-x); }
void del(int &x, int y, int l, int r, int pos) {
    x = ++tot;
    siz[x] = siz[y] - 1; lc[x] = lc[y]; rc[x] = rc[y];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) del(lc[x], lc[y], l, mid, pos);
    else del(rc[x], rc[y], mid + 1, r, pos);
}
void ins(int &x, int y, int l, int r, int pos) {
    x = ++tot;
    siz[x] = siz[y] + 1; lc[x] = lc[y]; rc[x] = rc[y];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) ins(lc[x], lc[y], l, mid, pos);
    else ins(rc[x], rc[y], mid + 1, r, pos);
}
void DELETE(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i)) del(root[i], root[i], 1, size, val);
}
void INSERT(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i)) ins(root[i], root[i], 1, size, val);
}
int x[35], xcnt;
int y[35], ycnt;
int query(int l, int r, int k) {
    if (l == r) return l;
    int ls = 0, mid = (l + r) >> 1;
    for (int i = 0; i < xcnt; ++i) ls += siz[lc[x[i]]];
    for (int i = 0; i < ycnt; ++i) ls -= siz[lc[y[i]]];
    if (k <= ls) {
        for (int i = 0; i < xcnt; ++i) x[i] = lc[x[i]];
        for (int i = 0; i < ycnt; ++i) y[i] = lc[y[i]];
        query(l, mid, k);
    } else {
        for (int i = 0; i < xcnt; ++i) x[i] = rc[x[i]];
        for (int i = 0; i < ycnt; ++i) y[i] = rc[y[i]];
        query(mid + 1, r, k - ls);
    }
}
int QUERY(int l, int r, int k) {
    xcnt = ycnt = 0;
    for (int i = r; i; i -= lowbit(i)) x[xcnt++] = root[i];
    for (int j = l - 1; j; j -= lowbit(j)) y[ycnt++] = root[j];
    return query(1, size, k);
}
int data[maxn][4], value[size];
struct Treap {
    int fa[size], c[size][2], rd[size], val[size], root, total, clock, id[size];
    void init() {
        root = total = clock = 0;
    }
    void rotate(int x) {
        int y = fa[x], z = fa[y], a = (c[y][1] == x), b = a ^ 1;
        if (z) c[z][c[z][1]==y]=x;
        fa[x]=z;fa[y]=x;fa[c[x][b]]=y;
        c[y][a]=c[x][b];c[x][b]=y;
        fa[0]=0;
    }
    void insert(int &now, int key, int father) {
        if (!now) {
            now = ++total;
            fa[total] = father;
            val[total] = key;
            rd[total] = rand() << 15 ^ rand();
            c[total][0] = c[total][1] = 0;
            while (fa[total] && rd[total] > rd[fa[total]]) rotate(total);
            if (!fa[total]) root = total;
            return;
        }
        if (val[now] == key) return;
        if (key < val[now]) insert(c[now][0], key, now);
        else insert(c[now][1], key, now);
    }
    void DFS(int x) {
        if (!x) return;
        DFS(c[x][0]);
        id[x] = ++clock;
        value[clock] = val[x];
        DFS(c[x][1]);
    }
    int find(int x, int key) {
        if (val[x] == key) return id[x];
        if (key < val[x]) return find(c[x][0], key);
        return find(c[x][1], key);
    }
    int operator [](int x) {
        return find(root, x);
    }
} M;
int main() {
    M.init();
    srand(20000926);
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i) {
        A[i] = getint();
        M.insert(M.root, A[i], 0);
    }
    char str[10];
    int a, b, c;
    for (int i = 1; i <= m; ++i) {
        scanf("%s", str);
        if (str[0] == 'Q') {
            a = getint(); b = getint(); c = getint();
            data[i][0] = 1; data[i][1] = a; data[i][2] = b; data[i][3] = c;
        } else {
            a = getint(); b = getint();
            data[i][0] = 0; data[i][1] = a; data[i][2] = b;
            M.insert(M.root, b, 0);
        }
    }
    int T = 0;
    M.DFS(M.root);
    for (int i = 1; i <= n; ++i) { INSERT(i, M[A[i]]); }
    for (int i = 1; i <= m; ++i) {
        if (data[i][0]) {
            a = data[i][1]; b = data[i][2]; c = data[i][3];
            printf("%d\n", value[QUERY(a, b, c)]);
        } else {
            a = data[i][1]; b = data[i][2];
            DELETE(a, M[A[a]]);
            INSERT(a, M[b]);
            A[a] = b;
        }
    }
    return 0;
}