浅谈树套树
p.s. 部分连接来自 CQBZOJ，非本校可能打不开。
例题 Dynamic Rankings
考虑没有修改操作，使用主席树。
那有修改就树套树。具体的，使用 BIT + persistent sgt。对于 \(Bit_i\)（\(root_i\)），代表了 \((i-lowbit_i,i]\) 的元素，就基于这个区间，开一个主席树。修改就修改 \(log_2 n\) 个主席树，查询也是在主席树上二分，所以时间复杂度：\(\mathcal {O}(nlog_2^2 n)\)。（详见代码）
p.s. 空间复杂度与时间复杂度同阶，但可能会有一个 \(\frac {1} {x}\) 的常数（好像 \(x\) 约等于 \(4\)？）。所以能开就开，不能开造最大数据视具体情况定吧。
#include
#include
#include
#include
#include
#define ls tree[p].L
#define rs tree[p].R
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 1e5 + 5;
struct Sgt {
int L, R, val;
}tree[MAXN * 60]; // ?
int n, m, root[MAXN], a[MAXN], tot;
vector op1, op2;
char s[6];
int add(int q, int l, int r, int x, int v) {
int p = ++ tot; tree[p] = tree[q];
if(l == r) { tree[p].val += v; return p; }
int mid = (l + r) >> 1;
if(x <= mid) ls = add(tree[q].L, l, mid, x, v);
else rs = add(tree[q].R, mid + 1, r, x, v);
tree[p].val = tree[ls].val + tree[rs].val; return p;
}
int ask(int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) >> 1, all = 0;
for(auto i : op1) all -= tree[tree[i].L].val;
for(auto i : op2) all += tree[tree[i].L].val;
if(all >= k) {
for(uint i = 0; i < op1.size(); i ++) op1[i] = tree[op1[i]].L;
for(uint i = 0; i < op2.size(); i ++) op2[i] = tree[op2[i]].L;
return ask(l, mid, k);
}
for(uint i = 0; i < op1.size(); i ++) op1[i] = tree[op1[i]].R;
for(uint i = 0; i < op2.size(); i ++) op2[i] = tree[op2[i]].R;
return ask(mid + 1, r, k - all);
}
int Lowbit(int x) { return x & (-x); }
void update(int x, int v, int k) { for(int i = x; i <= n; i += Lowbit(i)) root[i] = add(root[i], 0, 1e9, v, k); }
int askval(int l, int r, int k) {
op1.clear(); op2.clear();
for(int i = l - 1; i; i -= Lowbit(i)) op1.push_back(root[i]);
for(int i = r; i; i -= Lowbit(i)) op2.push_back(root[i]);
return ask(0, 1e9, k);
}
int main() {
int l, r, k;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), update(i, a[i], 1);
for(int i = 1; i <= m; i ++) {
scanf("%s", s);
if(s[0] == 'Q') scanf("%d%d%d", &l, &r, &k), printf("%d\n", askval(l, r, k));
else scanf("%d%d", &l, &k), update(l, a[l], -1), update(l, k, 1), a[l] = k;
}
return 0;
}
「ZJOI2013」K大数查询
区间修改+区间查询第 \(k\) 大。仿照BIT做区间修改，我们先将贡献差分，单点修改，维护 \(val=v,val1=v*(id-1)\)。查询时对于 \([l,r]\)，考虑 \([1,r]\) 的贡献为 \(\sum val*r-\sum val1\)，还是用主席树维护即可。
#include
#include
#include
#include
#include
#define ls tree[p].L
#define rs tree[p].R
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 5e4 + 5;
struct Sgt {
int L, R;
LL val, val1;
}tree[MAXN * 15 * 15]; // ?
int n, m, root[MAXN], a[MAXN], tot, ql, qr;
vector op1, op2;
char s[6];
int add(int q, int l, int r, int x, LL v, int f) {
int p = ++ tot; tree[p] = tree[q];
if(l == r) {
if(f == 1) tree[p].val1 += v;
else tree[p].val += v;
return p;
}
int mid = (l + r) >> 1;
if(x <= mid) ls = add(tree[q].L, l, mid, x, v, f);
else rs = add(tree[q].R, mid + 1, r, x, v, f);
tree[p].val = tree[ls].val + tree[rs].val; tree[p].val1 = tree[ls].val1 + tree[rs].val1; return p;
}
int ask(int l, int r, LL k) {
if(l == r) return l;
int mid = (l + r) >> 1;
LL all = 0;
for(auto i : op1) all -= tree[tree[i].R].val * ql - tree[tree[i].R].val1;
for(auto i : op2) all += tree[tree[i].R].val * qr - tree[tree[i].R].val1;
if(all >= k) {
for(uint i = 0; i < op1.size(); i ++) op1[i] = tree[op1[i]].R;
for(uint i = 0; i < op2.size(); i ++) op2[i] = tree[op2[i]].R;
return ask(mid + 1, r, k);
}
for(uint i = 0; i < op1.size(); i ++) op1[i] = tree[op1[i]].L;
for(uint i = 0; i < op2.size(); i ++) op2[i] = tree[op2[i]].L;
return ask(l, mid, k - all);
}
int Lowbit(int x) { return x & (-x); }
void update(int x, int v, int k) { for(int i = x; i <= n; i += Lowbit(i)) root[i] = add(root[i], -n, n, v, (x - 1ll) * k, 1), root[i] = add(root[i], -n, n, v, k, 2); }
int askval(int l, int r, LL k) {
op1.clear(); op2.clear(); ql = l - 1; qr = r;
for(int i = l - 1; i; i -= Lowbit(i)) op1.push_back(root[i]);
for(int i = r; i; i -= Lowbit(i)) op2.push_back(root[i]);
return ask(-n, n, k);
}
int main() {
int f, l, r;
LL c;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d%lld", &f, &l, &r, &c);
if(f == 1) update(l, c, 1), update(r + 1, c, -1);
else printf("%d\n", askval(l, r, c));
}
return 0;
}
「BZOJ2989」数列
根据数学知识，45°旋转坐标轴，\((x,y)\)->\((\sqrt 2 (x-y),\sqrt 2 (x+y))\) -> \((x-y,x+y)\) 转化为区间数点。
BIT 套 Sgt，单修+区查。
二逼平衡树
此题为何不能使用 BIT + Sgt？因为此题统计贡献时不满足区间加法。所以这里可以使用：
- Sgt（下标）+ Sgt（值域）
- Sgt（值域）+ Sgt（下标）
- Sgt（下标）+ 平衡树（维护值）
All Satisfy：时间：\(\mathcal {O}(nlog^2_2)\)，空间 \(\mathcal {O}(nlog^2_2)\)。
[FJOI2015]火星商店问题
\({\mathcal {Way1}}\)：