题目描述
The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads $N$ numbers from the input.
- Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.
题意概述
有一个长度为$N$的数列。有$M$次操作,每次操作询问数列第$i$项到第$j$项之间的第$k$小值,或者将第$i$项修改为$t$。
数据范围:$1 \le N \le 50000, \; 1 \le M \le 10000$。
内存限制:$32$M。
算法分析
对于这种询问区间第$k$小值的题目,很容易想到主席树。但由于主席树是一种类似前缀和的结构,一次修改操作需要修改$O(N)$棵线段树。这显然不是我们所希望的。
既然主席树类似前缀和,那么就可以借用维护前缀和的工具——树状数组。把树状数组的每个节点看成一棵线段树,这样一次修改操作就只需要修改$O(\log N)$棵线段树,时间复杂度为$O(\log^2N)$。而询问操作需要先把该询问在树状数组上用到的节点提取出来(有$O(\log N)$个),然后利用类似主席树的方法二分,时间复杂度也是$O(\log^2N)$。
但是!这题的内存限制非常小,接受不了$O((N+M)\log^2N)$的空间复杂度。再考虑主席树,它的空间复杂度是$O(N\log N)$的。因此可以对原序列建立静态的主席树,对修改操作利用树状数组维护,这样空间复杂度降至$O(N\log N+M\log^2N)$,可以通过。
代码
/* * Beware of Bigfoot! */ #include <algorithm> #include <cstdio> #include <cstring> #include <map> #include <vector> static int const N = 60005; static int const NM = 2000000; int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N]; struct Query { int o, i, j, k; } q[N]; struct SegmentTree { int ch[2], sum; } nd[NM]; int create(int rt = 0) { return nd[++nn] = nd[rt], nn; } int arr_insert(int rt, int p) { rt = create(rt), ++nd[rt].sum; int L = 0, R = N; for (int cur = rt; L < R;) { int MID = L + R >> 1, b = p > MID; nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum, cur = nd[cur].ch[b]; b ? L = MID + 1 : R = MID; } return rt; } void bit_insert(int &rt, int p, int v) { if (rt == 0) rt = create(); nd[rt].sum += v; int L = 0, R = N; for (int cur = rt; L < R;) { int MID = L + R >> 1, b = p > MID; if (nd[cur].ch[b] == 0) nd[cur].ch[b] = create(); nd[nd[cur].ch[b]].sum += v; int tmp = nd[cur].ch[b]; cur = tmp, b ? L = MID + 1 : R = MID; } } int bit_add(int p, int v, int c) { for (; p <= n; p += p & -p) bit_insert(bit_rt[p], v, c); } int main() { int T; scanf("%d", &T); for (; T--;) { std::map<int, int> mp; memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), mp[a[i]] = 0; for (int i = 1; i <= m; ++i) { char c; scanf(" %c", &c); if (c == 'Q') q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k); else q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0; } int cnt = 0; for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) rec[cnt] = it->first, it->second = cnt++; for (int i = 1; i <= n; ++i) arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]); for (int i = 1; i <= m; ++i) { if (q[i].o == 0) { std::vector<int> a, b; a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]); for (int p = q[i].i - 1; p; p -= p & -p) a.push_back(bit_rt[p]); for (int p = q[i].j; p; p -= p & -p) b.push_back(bit_rt[p]); int L = 0, R = N; for (; L < R;) { int sum = 0; for (int i = 0; i < a.size(); ++i) sum -= nd[nd[a[i]].ch[0]].sum; for (int i = 0; i < b.size(); ++i) sum += nd[nd[b[i]].ch[0]].sum; int MID = L + R >> 1; if (sum < q[i].k) { L = MID + 1, q[i].k -= sum; for (int i = 0; i < a.size(); ++i) a[i] = nd[a[i]].ch[1]; for (int i = 0; i < b.size(); ++i) b[i] = nd[b[i]].ch[1]; } else { R = MID; for (int i = 0; i < a.size(); ++i) a[i] = nd[a[i]].ch[0]; for (int i = 0; i < b.size(); ++i) b[i] = nd[b[i]].ch[0]; } } printf("%d\n", rec[L]); } else bit_add(q[i].i, mp[a[q[i].i]], -1), bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1); } } return 0; }