樹套樹全家桶
樹套樹
概念
顧名思義，一個樹套著另一個樹(bushi)
eg. 維護一個線段樹，并且對于每一個節用平衡樹進行維護
樹套樹有很多種，外層的樹可能有很多種，常見的是線段樹與樹狀數組，內層的樹最常見的是平衡樹，也有可能是其他的
例題
T1
有以下的兩種操作：
- \(1 \ pos \ x\) 將 \(pos\) 位置的數改成 \(x\)
- \(2\ l\ r\ x\) 查詢 \(x\) 在 \([l,r]\) 小于 \(x\) 的最大值
分析
求區間內的小于 \(x\) 的最大值很容易想到用 \(multiset\) 中的 \(bound\) 來維護，但是如果這個區間不固定，那就只能再套一層線段樹來維護了，對于任意一個區間，用線段樹來湊就好了，對于查詢，將所覆蓋的區間的 \(multiset\) 進行調用，時間復雜度:\(O(log_n^2)\)，對于修改：將包含這個點的左右區間的 \(multiset\) 先刪去原來的數，再插入新的數，時間復雜度一樣。
代碼
真的很難調.....
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50010;
const int M = N << 2;
const int INF = 1e9;
int n, m;
struct Tree
{
int l, r;
multiset<int> s;
}tr[M];
int w[N];
void build(int u, int l, int r)
{
tr[u] = {l, r};
tr[u].s.insert(-INF);
tr[u].s.insert(INF);
for(int i = l ; i <= r ; i ++ ) tr[u].s.insert(w[i]);
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void change(int u, int p, int x)
{
tr[u].s.erase(tr[u].s.find(w[p]));
tr[u].s.insert(x);
if(tr[u].l == tr[u].r) return;
int mid = tr[u].l + tr[u].r >> 1;
if(p <= mid) change(u << 1, p, x);
else change(u << 1 | 1, p, x);
}
int query(int u, int a, int b, int x)
{
if(tr[u].l >= a && tr[u].r <= b)
{
auto it = tr[u].s.lower_bound(x);
--it;
return *it;
}
int mid = tr[u].l + tr[u].r >> 1, res = -INF;
if(a <= mid) res = max(res, query(u << 1, a, b, x));
if(b > mid) res = max(res, query(u << 1 | 1, a, b, x));
return res;
}
signed main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++ ) cin >> w[i];
build (1, 1, n);
while (m -- )
{
int op, a, b, x;
cin >> op;
if (op == 1)
{
cin >> a >> x;
change(1, a, x);
w[a] = x;
}
else
{
cin >> a >> b >> x;
cout << query(1, a, b, x) << endl;
}
}
return 0;
}
T2
- \(1 \ l \ r \ k\) 查詢 \(x\) 在 \(l, r\) 中的排名
- \(2 \ l \ r\ k\) 查詢 \(l, r\) 中排名為 \(k\) 的值
- \(3\ pos\ x\) 將 \(pos\) 的位置上的數改為 \(x\)
- \(4\ l \ r \ x\) 查詢 \(x\) 在 \(l, r\) 中的前驅
- \(5\ l\ r\ x\) 查詢 \(x\) 在 \(l, r\) 中的后繼
分析
后兩個操作就很簡單用線段樹來套 \(multiset\) 就好了， 但是 還有前兩個操作，就不能偷懶了 \(QWQ\), 就只能用平衡樹了，(因為平衡樹的本質就是 動態 去維護一個區間)， 那怎么維護呢？對于排名：其實就是算有幾個數比 \(x\) 小，把所包含的區間的平衡樹調用出來，然后加起來就好了， 時間復雜度 : \(O(log_n^2)\),對于第 \(k\) 小數：我們是沒有辦法照貓畫虎， 不能將區間先劃分出來，然后；累加在一起我們只能用 二分答案， 用上第一問的操作，如果\(mid\) 比 \(x\) 小就往大的去二分，否則就往小的去二分，時間復雜度：\(O(log_n^3)\) (學過權值線段樹套線段樹的別叫！)，至于哪種平衡樹? \(treap\) 行，\(splay\) 行, \(fhq-treap\) 也行....,剩下的就是普通操作了。
代碼
又臭又長！！！
我吐啦！！！！！！！！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
const int INF = 1e9;
int n, m;
struct Node
{
int s[2], p, v;
int size;
void init(int _v, int _p)
{
v = _v, p = _p;
size = 1;
}
}tr[N];
int L[N], R[N], T[N], idx;
int w[N];
void pushup(int x)
{
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void splay(int& root, int x, int k)
{
while(tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if(z != k)
if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if(k == 0) root = x;
}
void insert(int& root, int v)
{
int u = root, p = 0;
while(u) p = u, u = tr[u].s[v > tr[u].v];
u = ++ idx;
if(p) tr[p].s[v > tr[p].v] = u;
tr[u].init(v, p);
splay(root, u, 0);
}
int get_k(int root, int v)
{
int u = root, res = 0;
while(u)
{
if(tr[u].v < v) res += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
else u = tr[u].s[0];
}
return res;
}
void update(int& root, int x, int y)
{
int u = root;
while(u)
{
if(tr[u].v == x) break;
if(tr[u].v < x) u = tr[u].s[1];
else u = tr[u].s[0];
}
splay(root, u, 0);
int l = tr[u].s[0], r = tr[u].s[1];
while(tr[l].s[1]) l = tr[l].s[1];
while(tr[r].s[0]) r = tr[r].s[0];
splay(root, l, 0), splay(root, r, l);
tr[r].s[0] = 0;
pushup(r), pushup(l);
insert(root, y);
}
void build(int u, int l, int r)
{
L[u] = l, R[u] = r;
insert(T[u], -INF);
insert(T[u], INF);
for(int i = l; i <= r; i ++ ) insert(T[u], w[i]);
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
int query(int u, int a, int b, int x)
{
if(L[u] >= a && R[u] <= b) return get_k(T[u], x) - 1;
int mid = L[u] + R[u] >> 1, res = 0;
if(a <= mid) res += query(u << 1, a, b, x);
if(b > mid) res += query(u << 1 | 1, a, b, x);
return res;
}
void change(int u, int p, int x)
{
update(T[u], w[p], x);
if(L[u] == R[u]) return;
int mid = L[u] + R[u] >> 1;
if(p <= mid) change(u << 1, p, x);
else change(u << 1 | 1, p, x);
}
int get_pre(int root, int v)
{
int u = root, res = -INF;
while(u)
{
if(tr[u].v < v) res = max(res, tr[u].v), u = tr[u].s[1];
else u = tr[u].s[0];
}
return res;
}
int get_suc(int root, int v)
{
int u = root, res = INF;
while(u)
{
if(tr[u].v > v) res = min(res, tr[u].v), u = tr[u].s[0];
else u = tr[u].s[1];
}
return res;
}
int query_pre(int u, int a, int b, int x)
{
if(L[u] >= a && R[u] <= b) return get_pre(T[u], x);
int mid = L[u] + R[u] >> 1, res = -INF;
if(a <= mid) res = max(res, query_pre(u << 1, a, b, x));
if(b > mid) res = max(res, query_pre(u << 1 | 1, a, b, x));
return res;
}
int query_suc(int u, int a, int b, int x)
{
if(L[u] >= a && R[u] <= b) return get_suc(T[u], x);
int mid = L[u] + R[u] >> 1, res = INF;
if(a <= mid) res = min(res, query_suc(u << 1, a, b, x));
if(b > mid) res = min(res, query_suc(u << 1 | 1, a, b, x));
return res;
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
build(1, 1, n);
while(m -- )
{
int op, a, b, x;
cin >> op;
if (op == 1)
{
cin >> a >> b >> x;
cout << query(1, a, b, x) + 1 << endl;
}
else if (op == 2)
{
cin >> a >> b >> x;
int l = 0, r = 1e8;
while (l < r)
{
int mid = l + r + 1 >> 1;
if(query(1, a, b, mid) + 1 <= x) l = mid;
else r = mid - 1;
}
cout << r << endl;
}
else if (op == 3)
{
cin >> a >> x;
change(1, a, x);
w[a] = x;
}
else if (op == 4)
{
cin >> a >> b >> x;
cout << query_pre(1, a, b, x) << endl;
}
else
{
cin >> a >> b >> x;
cout << query_suc(1, a, b, x) << endl;
}
}
return 0;
}
T3
\(1\ a\ b\ c\)： 將 \(a\)到 \(b\) 中的每個位置都加長一個數 \(c\)
\(2\ a\ b\ c\)： 詢問 \(a\) 到 \(b\) 位置中的第 \(k\) 大數
請注意，這個位置上可以放很多的數
分析
用線段樹套平衡樹好像不太好做的樣子~主要是線段樹套平衡樹的時間復雜度是 $O(nlog_n^3),時間太慢，我們就做一個 權值線段樹（又稱主席樹）套線段樹！
普通線段樹是以下標為端點，維護下標，對于權值線段樹，我們以數值為端點，我們就維護下標，但怎么維護呢？答案是線段樹bushi
對于加入，因為一個相同的權值是在權值線段樹上的一個點，我們就只需要修改 $O(log_n) $ 個普通的線段樹，對于每個普通線段樹，就是將這段都加一，其實就是區間修改,用個懶標記就好了！時間復雜度 \(O(log_n^2)\)
再考慮查詢第 \(k\) 大數，考慮在線段樹上二分，因為是第 \(k\) 大數，所以先考慮大的那一邊，那怎么判斷下標在 \([a, b]\) 內，權值在 \([l, r]\) 內的數的個數呢？其實這個個數就是這個權值線段數上 \([l,r]\) 這個區間上的普通線段樹的 \([a,b]\) 段的數之和，即區間求和，直接做就好了, 時間復雜度 \(O(log_n^2)\)
這樣子，你的代碼時間復雜度就可以吞掉一個 \(O(log_n)\), 成為 \(nlog_n^2\) 的優秀代碼，但是，打起來要吐血呀！！！！
當你做完了這些，結果內存一算，哎呀，爆了\((T(n \times n)\), 能不爆嗎？（bushi , 所以我們還要 動態開點， 開不開心~~（/(ㄒoㄒ)/）
代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50010;
const int P = N * 17 * 17;
const int M = N * 4;
int n, m;
struct Tree
{
int l, r;
int sum, add;
}tr[P];
int L[M], R[M], T[M], idx;
struct Query
{
int op, a, b, c;
}q[N];
vector<int> nums;
int get(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
void build(int u, int l, int r)
{
L[u] = l;
R[u] = r;
T[u] = ++ idx;
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
// 因為只要區間加，區間求和，我們就可以標記永久化，但我不會告訴你^v^
int intersection(int a, int b, int c, int d)
{
return min(b, d) - max(a, c) + 1;
}
void update(int u, int l, int r, int pl, int pr)
{
tr[u].sum += intersection(l, r, pl, pr);
if(l >= pl && r <= pr)
{
tr[u].add ++ ;
return;
}
int mid = l + r >> 1;
if(pl <= mid)
{
if(!tr[u].l) tr[u].l = ++ idx;
update(tr[u].l, l, mid, pl, pr);
}
if(pr > mid)
{
if(!tr[u].r) tr[u].r = ++ idx;
update(tr[u].r, mid + 1, r, pl, pr);
}
}
void change(int u, int a, int b, int c)
{
update(T[u], 1, n, a, b);
if(L[u] == R[u]) return;
int mid = L[u] + R[u] >> 1;
if(c <= mid) change(u << 1, a, b, c);
else change(u << 1 | 1, a, b, c);
}
int get_sum(int u, int l, int r, int pl, int pr, int add)
{
if(l >= pl && r <= pr) return tr[u].sum + (r - l + 1) * add;
int mid = l + r >> 1;
int res = 0;
add += tr[u].add;
if(pl <= mid)
{
if(tr[u].l) res += get_sum(tr[u].l, l, mid, pl, pr, add);
else res += intersection(l, mid, pl, pr) * add;
}
if(pr > mid)
{
if(tr[u].r) res += get_sum(tr[u].r, mid + 1, r, pl, pr, add);
else res += intersection(mid + 1, r, pl, pr) * add;
}
return res;
}
int query(int u, int a, int b, int c)
{
if(L[u] == R[u]) return R[u];
int mid = L[u] + R[u] >> 1;
int k = get_sum(T[u << 1 | 1], 1, n, a, b, 0);
if(k >= c) return query(u << 1 | 1, a, b, c);
return query(u << 1, a, b, c - k);
}
signed main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++ )
{
cin >> q[i].op >> q[i].a >> q[i].b >> q[i].c;
if(q[i].op == 1) nums.push_back(q[i].c);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
build(1, 0, nums.size() - 1);
for(int i = 0; i < m; i ++ )
{
int op = q[i].op, a = q[i].a, b = q[i].b, c = q[i].c;
if(op == 1) change(1, a, b, get(c));
else cout << nums[query(1, a, b, c)] << endl;
}
return 0;
}
題單
還沒有看到呢...
如果有好題單，不介意的話可以給我，在線等，急，謝謝！
浙公網安備 33010602011771號