[BZOJ 1901] Dynamic Rankings

树状数组套主席树。

考虑无修改求区间第 K 大的情况:因为主席树之间支持相加减,故可以维护一些包含 1~i 的线段树,计算它们的树前缀和,从而快速得到区间 [l, r] 中的第 K 大数。

考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。

类似地,我们可以维护一个树状数组,但线段树记录的不再是前缀和,而是树状数组的辅助数组的值。

这样就能做到带修改的区间第 K 大值查询了。

Reference:

http://blog.csdn.net/u014664226/article/details/47839973

代码如下:


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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

inline void set_file_IO(string);
inline void close_IO(void);
inline void work(void);

int main(void) {
    #ifndef ONLINE_JUDGE
        set_file_IO("dynrank");
    #endif
    //ios::sync_with_stdio(false);
    work();
    #ifndef ONLINE_JUDGE
        close_IO();
    #endif
    return 0;
}

const int nSize = 50000 + 100, mSize = 10000 + 100;

struct Node {
    int lc, rc, sum;
} tree[nSize * 40];
int root[nSize<<1];

int prefix[2][100];
int p[2];

int q[mSize][4];

int a[nSize];
int val[nSize+mSize];

int nodeCnt = 0;

inline int lowbit(const int x) {
    return x & -x;
}

inline int new_node(int _sum, int _lc, int _rc) {
    const int id = ++nodeCnt;
    tree[id].sum = _sum;
    tree[id].lc = _lc;
    tree[id].rc = _rc;
    return id;
}

// [l, r]

void build(int &root, int oldRoot, int l, int r, int pos) {
    root = new_node(tree[oldRoot].sum+1, tree[oldRoot].lc, tree[oldRoot].rc);
    if (l == r) {
        return ;
    }
    const int mid = (l+r) >> 1;
    if (pos <= mid) {
        build(tree[root].lc, tree[oldRoot].lc, l, mid, pos);
    } else {
        build(tree[root].rc, tree[oldRoot].rc, mid+1, r, pos);
    }
}

void insert(int &root, int l, int r, int pos, int val) {
    if (!root) {
        root = new_node(0, 0, 0);
    }
    tree[root].sum += val;
    if (l == r) {
        return ;
    }
    const int mid = (l+r) >> 1;
    if (pos <= mid) {
        insert(tree[root].lc, l, mid, pos, val);
    } else {
        insert(tree[root].rc, mid+1, r, pos, val);
    }
}

int query(int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int mid = (l+r) >> 1, sum = 0;
    for (int j=0, flg=-1; j<2; flg+=2, ++j) { // j = 0, 1
        for (int i=0; i<=p[j]; ++i) {
            sum += tree[tree[prefix[j][i]].lc].sum;
        }
        sum *= flg;
    }
    if (k <= sum) {
        for (int j=0; j<2; ++j) { // j = 0, 1
            for (int i=0; i<=p[j]; ++i) {
                prefix[j][i] = tree[prefix[j][i]].lc;
            }
        }
        return query(l, mid, k);
    }
    for (int j=0; j<2; ++j) { // j = 0, 1
        for (int i=0; i<=p[j]; ++i) {
            prefix[j][i] = tree[prefix[j][i]].rc;
        }
    }
    return query(mid+1, r, k-sum);
}

inline void single(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    nodeCnt = 0;
    int valSize = n;
    for (int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        val[i] = a[i];
    }
    for (int i=1; i<=m; ++i) {
        char opt[10];
        scanf("%s %d%d", opt, &q[i][1], &q[i][2]);
        q[i][0] = opt[0];
        if (opt[0] == 'Q') {
            scanf("%d", &q[i][3]);
        } else {
            val[++valSize] = q[i][2];
        }
    }
    sort(val+1, val+valSize+1);
    valSize = unique(val+1, val+valSize+1) - (val+1);
    for (int i=1; i<=n; ++i) {
        a[i] = lower_bound(val+1, val+valSize+1, a[i]) - val;
    }
    for (int i=1; i<=n; ++i) {
        build(root[i+n], root[i+n-1], 1, valSize, a[i]);
    }
    for (int i=1; i<=m; ++i) {
        if (q[i][0] == 'Q') {
            p[0] = p[1] = 0;
            prefix[1][0] = root[q[i][2]+n];
            prefix[0][0] = root[q[i][1]-1 == 0? 0: q[i][1] - 1 + n];
            for (int j=q[i][2]; j; j-=lowbit(j)) {
                prefix[1][++p[1]] = root[j];
            }
            for (int j=q[i][1]-1; j; j-=lowbit(j)) {
                prefix[0][++p[0]] = root[j];
            }
            printf("%d\n", val[query(1, valSize, q[i][3])]);
        } else {
            for (int j=q[i][1]; j<=n; j+=lowbit(j)) {
                insert(root[j], 1, valSize, a[q[i][1]], -1);
            }
            a[q[i][1]] = lower_bound(val+1, val+valSize+1, q[i][2]) - val;
            for (int j=q[i][1]; j<=n; j+=lowbit(j)) {
                insert(root[j], 1, valSize, a[q[i][1]], 1);
            }
        }
    }
    memset(root, 0, sizeof root);
}

inline void work(void) {
    int cases;
    scanf("%d", &cases);
    while (cases --> 0) {
        single();
    }
}

inline void set_file_IO(string name) {
    freopen((name + ".in" ).c_str(), "r", stdin );
    freopen((name + ".out").c_str(), "w", stdout);
}

inline void close_IO(void) {
    fclose(stdin);
    fclose(stdout);
}

发表评论

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