Tip：建議完成 Luogu P3919 後閱讀。
首先我們想一想，如何用線段樹求數列 \(k\) 小值。
我們可以建一棵權值線段樹，由於權值線段樹的結點表示的是該結點指向的區間的數的數量，我們就可以直接使用一種類似二分的方法查詢 \(k\) 小值。
假如你要查詢第 \(5\) 小的數，如果你發現左兒子有 \(4\) 個數，那麼就直接放棄左兒子去右兒子查詢；反之，如果左兒子有 \(7\) 個數，那麼就直接放棄右兒子在左兒子查詢。
我們把這個方法推廣到區間，顯然，如果我們擁有一個區間的權值線段樹，就可以查詢該區間的 \(k\) 小值。
如何獲得區間的權值線段樹呢？
也許，我們可以把這個數列 \(a_{1 \sim n}\) 的權值線段樹看作 \(a_1,a_2,\dots,a_n\) 各自的權值線段樹的字首和樹（把字首和的操作類比到樹上），我們用 \(sum_i\) 表示 \(a_{1 \sim i}\) 的權值線段樹的字首和樹，用 \(tree_{l\sim r}\) 表示區間 \(l \sim r\) 的權值線段樹。
顯然，我們可以利用字首和的性質來求一個區間的權值線段樹，即 \(tree_{l \sim r} = sum_r - sum_{l - 1}\)。
接下來我們引入可持久化線段樹，我們可以一個個地插入新的元素，從而獲得 \(n + 1\) 個版本的權值線段樹（第 \(0\) 個版本是空樹）。
這 \(n + 1\) 棵權值線段樹實質上就是字首和樹，接下來我們就可以直接獲得任意區間的權值線段樹來查詢區間 \(k\) 小值啦。
值域一般都很大，所以要記得要離散化哦。
時間複雜度 \(O(n \log n)\)
// 44-2 Baijian
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1005000;
int n,m,q;
// m 表示值域
int a[N],b[N];
struct Segment{
int l,r,sum;
}t[N<<2];
int root[N];
#define lid (t[id].l)
#define rid (t[id].r)
class Segment_Tree{
int tot = 0;
private:
int Clone(int id) {
tot ++;
t[tot] = t[id];
t[tot].sum += 1;
return tot;
}
public:
int Build(int id,int l,int r) {
id = ++tot;
if(l == r) {
t[id].sum = a[l];
return id;
}
int mid = (l + r) >> 1;
lid = Build(lid,l,mid);
rid = Build(rid,mid + 1,r);
return id;
}
int Update(int id,int l,int r,int val) {
id = Clone(id);
if(l == r)
return id;
int mid = (l + r) >> 1;
if(val <= mid)
lid = Update(lid,l,mid,val);
else
rid = Update(rid,mid + 1,r,val);
return id;
}
int Query(int l,int r,int L,int R,int val) {
int x = t[t[r].l].sum - t[t[l].l].sum;
if(L == R)
return L;
int mid = (L + R) >> 1;
if(x >= val)
return Query(t[l].l,t[r].l,L,mid,val);
else
return Query(t[l].r,t[r].r,mid + 1,R,val - x);
}
}tree;
int main() {
ios::sync_with_stdio(false);
cin >> n >> q;
for(int i = 1;i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1,b + n + 1);
m = unique(b + 1,b + n + 1) - (b + 1);
// 離散化
tree.Build(root[0],1,m);
for(int i = 1,x;i <= n; i++) {
x = lower_bound(b + 1,b + m + 1,a[i]) - b;
root[i] = tree.Update(root[i - 1],1,m,x);
}
for(int i = 1,l,r,k,ans;i <= q; i++) {
cin >> l >> r >> k;
ans = tree.Query(root[l - 1],root[r],1,m,k);
cout << b[ans] << "\n";
}
return 0;
}
與上一道模板相比，多了一個把 \(a_x\) 修改為 \(y\) 的操作。
實際上，動態主席樹是樹套樹，不過動態主席樹用到了與靜態主席樹類似的思想，即維護字首和。
我們先來看看單點修改。
假設要將 \(a_x\) 修改為 \(y\)，它將影響到根為 \(root_{x \sim n}\) 的字首和樹。要是暴力的話，我們就直接把 \(x\) 到 \(n\) 的字首和樹修改一下，\(a_x\) 位置的值 \(-1\)，\(y\) 位置的值 \(+1\)。
這樣的複雜度顯然不滿足要求。
我們要維護一個字首和，我們過去好像用樹狀陣列維護過單點修改的字首和，利用 \(\text{lowbit}\) 可以以 \(\log n\) 的複雜度進行區間修改，原先 \(O(n)\) 的外層修改優化成了 \(O(\log n)\)。
那我們就可以寫一個樹狀陣列套主席樹。
時間複雜度：\(O(n \log^2 n)\)，比線段樹套平衡樹少個 \(\log\)。
實現的思路是將修改操作用一棵主席樹存，在查詢時與初始的主席樹一併操作。
// 44-9 Baijian
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 6605000;
int n,m;
int tot = 0;
int a[N],b[N],cnt;
int cnt1,cnt2;
int Left[N],Right[N];
struct Option{
int op;
int l,r,k,x,y;
}q[N];
int Find(int x) {
// Discretizing
return (lower_bound(b + 1,b + cnt + 1,x) - b);
}
// Segment Tree
struct Segment{
int l,r,sum;
}t[N<<2];
int root[N],rt[N];
class Segment_Tree{
public:
void Update(int id1,int &id2,int l,int r,int pos,int val) {
if(!id2)
id2 = ++ tot;
t[id2].sum = t[id1].sum + val;
if(l == r)
return ;
int mid = (l + r) >> 1;
if(pos <= mid) {
t[id2].r = t[id1].r;
Update(t[id1].l,t[id2].l,l,mid,pos,val);
}
else {
t[id2].l = t[id1].l;
Update(t[id1].r,t[id2].r,mid + 1,r,pos,val);
}
return ;
}
int Query(int l,int r,int L,int R,int val) {
if(L == R)
return L;
int sum1 = 0,sum2 = 0;
for(int i = 1;i <= cnt1; i++)
sum1 += t[t[Left[i]].l].sum;
for(int i = 1;i <= cnt2; i++)
sum2 += t[t[Right[i]].l].sum;
int x = t[t[r].l].sum - t[t[l].l].sum + sum2 - sum1;
int mid = (L + R) >> 1;
if(x >= val) {
for(int i = 1;i <= cnt1; i++)
Left[i] = t[Left[i]].l;
for(int i = 1;i <= cnt2; i++)
Right[i] = t[Right[i]].l;
return Query(t[l].l,t[r].l,L,mid,val);
}
else {
for(int i = 1;i <= cnt1; i++)
Left[i] = t[Left[i]].r;
for(int i = 1;i <= cnt2; i++)
Right[i] = t[Right[i]].r;
return Query(t[l].r,t[r].r,mid + 1,R,val - x);
}
}
}tree;
// BIT
int lowbit(int x) {
return x & (-x);
}
void Add(int l,int r,int pos1,int pos2) {
for(int i = l;i <= r; i += lowbit(i))
tree.Update(root[i],root[i],1,cnt,pos1,-1);
for(int i = l;i <= r; i += lowbit(i))
tree.Update(root[i],root[i],1,cnt,pos2,1);
return ;
}
void Get(int l,int r) {
cnt1 = cnt2 = 0;
for(int i = l - 1;i; i -= lowbit(i))
Left[++cnt1] = root[i];
for(int i = r;i; i -= lowbit(i))
Right[++cnt2] = root[i];
return ;
}
void Clear() {
for(int i = 1;i <= tot; i++)
t[i].l = t[i].r = t[i].sum = 0;
for(int i = 1;i <= n; i++)
rt[i] = root[i] = 0;
tot = 0;
cnt = 0;
return ;
}
// main
signed main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--) {
cin >> n >> m;
for(int i = 1;i <= n; i++) {
cin >> a[i];
b[++cnt] = a[i];
}
char opt;
for(int i = 1;i <= m; i++) {
cin >> opt;
if(opt == 'Q') {
q[i].op = 1;
cin >> q[i].l >> q[i].r >> q[i].k;
}
else {
q[i].op = 2;
cin >> q[i].x >> q[i].y;
b[++cnt] = q[i].y;
}
}
// Discretizing
sort(b + 1,b + 1 + cnt);
cnt = unique(b + 1,b + 1 + cnt) - (b + 1);
for(int i = 1;i <= n; i++)
tree.Update(rt[i - 1],rt[i],1,cnt,Find(a[i]),1);
for(int i = 1;i <= m; i++) {
if(q[i].op == 1) {
Get(q[i].l,q[i].r);
int ans;
ans = tree.Query(rt[q[i].l - 1],rt[q[i].r],1,cnt,q[i].k);
cout << b[ans] << "\n";
}
else {
Add(q[i].x,n,Find(a[q[i].x]),Find(q[i].y));
a[q[i].x] = q[i].y;
}
}
Clear();
}
return 0;
}
給定一個長度為 \(n\) 的數列 \(a\)，進行 \(m\) 次詢問，每次詢問一個區間中是否存在一個長度為 \(k\) 的子數列（每次詢問的 \(k\) 值相等）。
判斷兩個區間是否相等，顯然我們可以用 \(\text{hash}\)。
我們把一個長度為 \(k\) 的區間的 \(\text{hash}\) 值看作一個元素，這道題實際上就轉化為了求給定區間中是否存在某個數。
由於每個測試點中 \(k\) 的值是一定的，那麼就可以直接預處理得到整個數列中任意連續 \(k\) 個數的 \(\text{hash}\)，然後把它塞進樹。
我們可以用主席樹獲取任意區間的權值線段樹，直接在查詢區間的權值線段樹中尋找查詢數列的 \(\text{hash}\) 即可。
// 44 - 1 BZOJ3207 Baijian
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 4000500;
int n,m,k;
// Hash
typedef unsigned long long ULL;
ULL base = 131;
ULL Hash[N],p[N];
ULL Get(int l,int r) {
return Hash[r] - Hash[l - 1] * p[r - l + 1];
}
// Segment Tree
struct Segment{
int l,r,sum;
}t[N<<2];
int root[N];
#define lid (t[id].l)
#define rid (t[id].r)
class Segment_Tree{
int tot = 0;
private:
int Clone(int id) {
tot ++;
t[tot] = t[id];
t[tot].sum += 1;
return tot;
}
public:
int Update(int id,ULL l,ULL r,ULL val) {
id = Clone(id);
if(l >= r)
return id;
ULL mid = l + ((r - l) >> 1);
if(val <= mid)
lid = Update(lid,l,mid,val);
else
rid = Update(rid,mid + 1,r,val);
return id;
}
bool Query(int l,int r,ULL L,ULL R,ULL val) {
if(L >= R) {
if(t[r].sum != t[l].sum)
return 1;
return 0;
}
int x = t[r].sum - t[l].sum;
if(!x)
return 0;
ULL mid = L + ((R - L) >> 1);
if(val <= mid)
Query(t[l].l,t[r].l,L,mid,val);
else
Query(t[l].r,t[r].r,mid + 1,R,val);
}
}tree;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> k;
for(int i = 1,x;i <= n; i++) {
cin >> x;
Hash[i] = base * Hash[i - 1] + x;
}
p[0] = 1;
for(int i = 1;i <= n; i++)
p[i] = p[i - 1] * base;
for(int i = k;i <= n; i++) {
ULL x = Get(i - k + 1,i);
root[i] = tree.Update(root[i - 1],0,ULLONG_MAX,x);
}
for(int i = 1,l,r;i <= m; i++) {
cin >> l >> r;
ULL tmp = 0;
for(int j = 1,x;j <= k; j++) {
cin >> x;
tmp = tmp * base + x;
}
if(tree.Query(root[l - 1],root[r],0,ULLONG_MAX,tmp))
cout << "No\n";
else
cout << "Yes\n";
}
return 0;
}
HH 的項鍊強制線上版。
給定一個顏色序列，詢問 \([l,r]\) 之間出現了多少種顏色，強制線上。
和 HH 的項鍊思路一致。
依次遍歷這個數列，若當前數在前面出現過，就把前面那個數的位置 \(-1\)，把當前位置 \(+1\)；若當前數在前面沒有出現過，就直接把當前位置 \(+1\)。
// 44-3 Baijian
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 5005000;
int n,m;
int last[N],ans;
struct Segment{
int l,r,sum;
}t[N<<2];
int root[N];
#define lid (t[id].l)
#define rid (t[id].r)
class Segment_Tree{
int tot = 0;
private:
int Clone(int id,int val) {
tot ++;
t[tot] = t[id];
t[tot].sum += val;
return tot;
}
public:
int Update(int id,int l,int r,int pos,int val) {
id = Clone(id,val);
if(l >= r)
return id;
int mid = (l + r) >> 1;
if(pos <= mid)
lid = Update(lid,l,mid,pos,val);
else
rid = Update(rid,mid + 1,r,pos,val);
return id;
}
int Query(int id,int l,int r,int pos) {
if(l == r)
return t[id].sum;
int mid = (l + r) >> 1;
if(pos <= mid)
return Query(lid,l,mid,pos) + t[rid].sum;
else
return Query(rid,mid + 1,r,pos);
/*
* 需要向左兒子遞迴時
* 我們發現右兒子肯定在我們查詢區間裡
* （因為你是從 root[r] 找的啊）
* 所以要加上 t[rid].sum
*/
}
}tree;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1,col;i <= n; i++) {
cin >> col;
if(!last[col]) {
root[i] = tree.Update(root[i - 1],1,n,i,1);
last[col] = i;
}
else {
int tmp = tree.Update(root[i - 1],1,n,last[col],-1);
root[i] = tree.Update(tmp,1,n,i,1);
last[col] = i;
}
}
for(int i = 1,l,r;i <= m; i++) {
cin >> l >> r;
l = (l + ans) % n + 1;
r = (r + ans) % n + 1;
if(l > r)
swap(l,r);
ans = tree.Query(root[r],1,n,l);
cout << ans << "\n";
}
return 0;
}
給定一棵 \(n\) 個節點的樹，每個點有一個權值。有 \(m\) 個詢問，每次給你 \(u,v,k\)，你需要回答 \(u \text{ xor last}\) 和 \(v\) 這兩個節點間第 \(k\) 小的點權（其中 \(\text{last}\) 是上一個詢問的答案）。
這不是樹上字首和？由於主席樹擁有字首和的性質，所以我們可以直接樹上差分獲取 \(u\) 到 \(v\) 這條路徑的權值線段樹，然後在這個權值線段樹中查詢區間 \(k\) 小值。
前置芝士：\(\text{LCA}\)，樹上差分
// P2633
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 9005000;
int n,m,S;
int a[N],b[N];
int last = 0;
// Discretizing
int Find(int x) {
return (lower_bound(b + 1,b + S + 1,x) - b);
}
// Graph
struct Edge{
int next,to;
}e[N << 1];
int cnt,h[N];
void add(int u,int v) {
cnt++;
e[cnt].next = h[u];
h[u] = cnt;
e[cnt].to = v;
}
// Segment_Tree
struct Segment{
int l,r,sum;
}t[N<<1];
int tot = 0;
class Segment_Tree{
public:
void Build(Segment &id,int l,int r) {
id.sum = 0;
if(l == r)
return ;
int mid = (l + r)>>1;
id.l = ++tot;
Build(t[id.l],l,mid);
id.r = ++tot;
Build(t[id.r],mid + 1,r);
return ;
}
void Update(Segment pre,Segment &now,int l,int r,int pos) {
now.sum = pre.sum + 1;
if(l == r)
return ;
int mid = (l + r) >> 1;
if(pos <= mid) {
now.l = ++tot;
Update(t[pre.l],t[now.l],l,mid,pos);
now.r = pre.r;
}
else {
now.r = ++tot;
Update(t[pre.r],t[now.r],mid + 1,r,pos);
now.l = pre.l;
}
return ;
}
int Query(Segment a,Segment b,Segment c,Segment d,int l,int r,int k) {
// u v lca(u,v) fa[lca(u,v)]
if(l == r)
return l;
int x = t[a.l].sum + t[b.l].sum - t[c.l].sum - t[d.l].sum;
int mid = (l + r) >> 1;
if(x >= k)
return Query(t[a.l],t[b.l],t[c.l],t[d.l],l,mid,k);
else
return Query(t[a.r],t[b.r],t[c.r],t[d.r],mid + 1,r,k - x);
}
}tree;
// lca
int root[N];
int dep[N];
int f[N][40];
void dfs(int u,int pre) {
root[u] = ++tot;
tree.Update(t[root[pre]],t[root[u]],1,S,Find(a[u]));
dep[u] = dep[pre] + 1;
f[u][0] = pre;
for(int i = 1;i <= 26; i++)
f[u][i] = f[f[u][i - 1]][i - 1];
for(int i = h[u];i; i = e[i].next) {
int v = e[i].to;
if(v != pre)
dfs(v,u);
}
}
int lca(int x,int y) {
if(dep[x] < dep[y])
swap(x,y);
for(int i = 26;i >= 0; i--)
if(dep[f[x][i]] >= dep[y])
x = f[x][i];
if(x == y)
return x;
for(int i = 26;i >= 0; i--)
if(f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1;i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
for(int i = 1,x,y;i < n; i++) {
cin >> x >> y;
add(x,y);
add(y,x);
}
// Discretizing
sort(b + 1,b + n + 1);
S = unique(b + 1,b + n + 1) - (b + 1);
root[0] = ++tot;
tree.Build(t[root[0]],1,S);
dfs(1,0);
for(int i = 1,u,v,k;i <= m; i++) {
cin >> u >> v >> k;
u = u ^ last;
int _lca = lca(u,v);
int fa_lca = f[_lca][0];
int ans = b[tree.Query(t[root[u]],t[root[v]],t[root[_lca]],t[root[fa_lca]],1,S,k)];
// 路徑的權值線段樹中查詢
cout << ans << "\n";
last = ans;
}
return 0;
}
多了一個在點 \(x\) 和點 \(y\) 之間連邊的操作，保證操作後仍然是一片森林。
對於查詢操作，保證 \(x\) 和 \(y\) 連通，且二者之間路徑上至少有 \(k\) 個點。
惱！
查詢？ 主席樹？
連邊？ LCT？
嗯，可以搞
\(\text{5 hours later} \dots\)
只有連邊操作，就是合併兩棵樹，我們來想想啟發式合併。
我們維護一下每個點所處的集合的大小，在連邊的時候，直接把小的集合合併到大的上面（感覺好暴力）。
複雜度 \(O( \text{能過} )\)，程式碼和上面那道題程式碼一脈相承（就是複製下來的）
但事實告訴我們，最好不要粘上一道題程式碼o(>﹏<)o
// 44-4
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 5005000;
int testcase;
int n,m,T;
int a[N],b[N];
int len,size[N];
// Graph
struct Edge{
int next,to;
}e[N<<1];
int h[N],cnt;
void Add(int u,int v) {
cnt ++;
e[cnt].next = h[u];
h[u] = cnt;
e[cnt].to = v;
}
// Segment Tree
struct Segment{
int l,r,sum;
}t[N<<1];
int tot = 0,root[N];
class Segment_Tree{
public:
void Update(Segment pre,Segment &now,int l,int r,int pos) {
now.sum = pre.sum + 1;
if(l == r)
return ;
int mid = (l + r) >> 1;
if(pos <= mid) {
now.l = ++tot;
Update(t[pre.l],t[now.l],l,mid,pos);
now.r = pre.r;
}
else {
now.r = ++tot;
Update(t[pre.r],t[now.r],mid + 1,r,pos);
now.l = pre.l;
}
return ;
}
int Query(Segment a,Segment b,Segment c,Segment d,int l,int r,int k) {
// u v lca(u,v) fa[lca(u,v)]
if(l == r)
return l;
int x = t[a.l].sum + t[b.l].sum - t[c.l].sum - t[d.l].sum;
int mid = (l + r) >> 1;
if(x >= k)
return Query(t[a.l],t[b.l],t[c.l],t[d.l],l,mid,k);
else
return Query(t[a.r],t[b.r],t[c.r],t[d.r],mid + 1,r,k - x);
}
}tree;
// Discretizing
int Find(int x) {
return (lower_bound(b + 1,b + len + 1,x) - b);
}
int dep[N];
int f[N][40];
int lca(int x,int y) {
if(dep[x] < dep[y])
swap(x,y);
for(int i = 26;i >= 0; i--)
if(dep[f[x][i]] >= dep[y])
x = f[x][i];
if(x == y)
return x;
for(int i = 26;i >= 0; i--)
if(f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
bool vis[N];
int fat[N];
void dfs(int x,int fa,int Anc) {
vis[x] = 1;
fat[x] = Anc;
// ancestor
// number of set
f[x][0] = fa;
dep[x] = dep[fa] + 1;
root[x] = ++ tot;
tree.Update(t[root[fa]],t[root[x]],1,n,Find(a[x]));
for(int i = 1;i <= 26; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = h[x];i; i = e[i].next) {
int to = e[i].to;
if(to == fa)
continue;
dfs(to,x,Anc);
size[x] += size[to];
}
return ;
}
int last = 0;
int main() {
ios::sync_with_stdio(false);
cin >> testcase;
cin >> n >> m >> T;
for(int i = 1;i <= n; i++) {
cin >> a[i];
b[i] = a[i];
size[i] = 1;
}
for(int i = 1,x,y;i <= m; i++) {
cin >> x >> y;
Add(x,y);
Add(y,x);
}
sort(b + 1,b + n + 1);
len = unique(b + 1,b + n + 1) - (b + 1);
for(int i = 1;i <= n; i++)
if(!vis[i])
dfs(i,0,i);
char op;
for(int i = 1,x,y,k;i <= T; i++) {
cin >> op;
cin >> x >> y;
x = x xor last;
y = y xor last;
if(op == 'Q') {
cin >> k;
k = k xor last;
int _lca = lca(x,y);
int fa_lca = f[_lca][0];
last = b[tree.Query(t[root[x]],t[root[y]],t[root[_lca]],t[root[fa_lca]],1,n,k)];
cout << last << "\n";
}
else {
Add(x,y);
Add(y,x);
if(size[fat[x]] < size[fat[y]]) {
size[fat[y]] += size[fat[x]];
dfs(x,y,fat[y]);
}
else {
size[fat[x]] += size[fat[y]];
dfs(y,x,fat[x]);
}
// Seemed like a Brute force
}
}
return 0;
}