本文共 4721 字，大约阅读时间需要 15 分钟。
有眼就行
动态主席树 和 整体二分 的模板题!
关于主席树的解法, 因为有单点修改, 所以我们要采用动态主席树. 具体方法就是, 把主席树中的存储方式采用树状数组的存储方式.
因此查询的时候, 原本是传入一个l - 1版本和一个当前版本r, 但是由于采用了树状数组的存储方式, 就要传入logn个版本. 修改同理.
整体二分
不得不说, 这题整体二分跑的是真的快!
//例题: 求动态区间第K小数 (静态树 + 动态树做法)//思路: 用树状数组的存储方式维护前缀和. 静态树记录初始情况, 动态树维护修改情况//时间复杂度: O((n + m)lognlogn) 空间复杂度: O(nlogn + mlognlogn)#include#define rep(i, n) for (int i = 1; i <= (n); ++i)using namespace std;typedef long long ll;const int N = 1E5 + 10, M = N * 17 * 17; // M为节点数int n, m;int w[N];vector v(1, -0x3f3f3f3f); int len = 0; //len为离散化后值域边界, 但不是树的边界.int find(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }struct operation { //操作离线 int tp, l, r, k; // x y N}; vector area;struct node { int l, r; int cou;}t[M];int rt[N], root[N], ind; //root是动态树, rt是静态树int build(int a, int tl, int tr, int p) { int x = ++ind; t[x] = t[p]; t[x].cou++; if (tl == tr) return x; int mid = tl + tr >> 1; if (a <= mid) t[x].l = build(a, tl, mid, t[p].l); else t[x].r = build(a, mid + 1, tr, t[p].r); return x;}void modify(int a, int c, int tl, int tr, int& x) { //修改动态树 if (!x) x = ++ind; t[x].cou += c; if (tl == tr) return; int mid = tl + tr >> 1; a <= mid ? modify(a, c, tl, mid, t[x].l) : modify(a, c, mid + 1, tr, t[x].r);}int query(int k, int tl, int tr, vector & p, vector & x) { //查询树中第k小 if (tl == tr) return tl; //查询类似单树查询, 只不过p和x都变成了数组(logn棵树) int cou = 0; for (auto& op : x) cou += t[t[op].l].cou; for (auto& op : p) cou -= t[t[op].l].cou; int mid = tl + tr >> 1; vector np, nx; if (cou >= k) { for (auto& op : p) np.push_back(t[op].l); for (auto& op : x) nx.push_back(t[op].l); return query(k, tl, mid, np, nx); } for (auto& op : p) np.push_back(t[op].r); for (auto& op : x) nx.push_back(t[op].r); return query(k - cou, mid + 1, tr, np, nx); //记得减去左边贡献}int lowbit(int x) { return x & -x; }void add(int x, int c) { for (int i = x; i <= n; i += lowbit(i)) modify(w[x], c, 1, len, root[i]);}int ask(int l, int r, int k) { vector np, nx; nx.push_back(rt[r]), np.push_back(rt[l - 1]); //推入静态树 for (int i = r; i; i -= lowbit(i)) nx.push_back(root[i]); for (int i = l - 1; i; i -= lowbit(i)) np.push_back(root[i]); //注意l - 1 return query(k, 1, len, np, nx);}int main(){ cin >> n >> m; rep(i, n) scanf("%d", &w[i]), v.push_back(w[i]); rep(i, m) { char s[2]; scanf("%s", s); if (*s == 'Q') { int l, r, k; scanf("%d %d %d", &l, &r, &k); area.push_back({ 1, l, r, k }); } else { int a, c; scanf("%d %d", &a, &c); area.push_back({ 2, a, c, NULL }); //注意存下标, 树状数组要根据位置修改 v.push_back(c); } } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); len = v.size() - 1; rep(i, n) { //建静态树 rt[i] = build(w[i] = find(w[i]), 1, len, rt[i - 1]); //add(i, 1); 如果不用build, 都用add, 则为纯动态树的方法.(费空间) } for (auto& op : area) { if (op.tp == 1) printf("%d\n", v[ask(op.l, op.r, op.k)]); else { add(op.l, -1); w[op.l] = find(op.r); //记得修改w数组 add(op.l, 1); } } return 0;}
#include#define rep(i, n) for (int i = 1; i <= (n); ++i)#define debug(a) cout << #a << " = " << a << endl;using namespace std;typedef long long ll;const int N = 1E5 + 10;int n, m;int w[N], res[N];struct operation { int tp, l, r, k, id; // a, c, f, NULL}; vector area;int t[N];int lowbit(int x) { return x & -x; }void add(int x, int c) { for (int i = x; i <= n; i += lowbit(i)) t[i] += c; }int ask(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res+= t[i]; return res;}int ask(int l, int r) { return ask(r) - ask(l - 1); }void fact(int l, int r, vector & q) { if (q.empty()) return; if (l == r) { for (auto& op : q) if (!op.tp) res[op.id] = l; return; } int mid = l + r >> 1; vector ql, qr; for (auto& op : q) { if (op.tp) { if (op.r <= mid) add(op.l, op.k), ql.push_back(op); else qr.push_back(op); } else { int cou = ask(op.l, op.r); if (cou >= op.k) ql.push_back(op); else op.k -= cou, qr.push_back(op); } } for (auto& op : ql) if (op.tp) add(op.l, -op.k); fact(l, mid, ql), fact(mid + 1, r, qr);}int main(){ cin >> n >> m; rep(i, n) { scanf("%d", &w[i]); area.push_back({ 1, i, w[i], 1, NULL }); } rep(i, m) { res[i] = -1; char s[2]; scanf("%s", s); if (*s == 'Q') { int l, r, k; scanf("%d %d %d", &l, &r, &k); area.push_back({ 0, l, r, k, i }); } else { int a, c; scanf("%d %d", &a, &c); area.push_back({ 1, a, w[a], -1, NULL }); w[a] = c; area.push_back({ 1, a, w[a], 1, NULL }); } } fact(0, 0x3f3f3f3f, area); rep(i, m) if (res[i] != -1) printf("%d\n", res[i]); return 0;}
转载地址：http://dnetz.baihongyu.com/