勢能線段樹
勢能線段樹包括了吉司機線段樹。思想就是正常線段樹可能遇到難 pushup 的情況，我們直接暴力遞歸，然后根據勢能分析說明這個暴力復雜度是均攤可接受的。
【勢能線段樹】
【例一】
題意：
支持三種操作。
-
單點修改。
-
區間對給定數取模。
-
區間求和。
\(n,q\le 10^5\)，時限 4s.
注意到一個事實：當 \(x\ge p\)，\(x\bmod p\le x/2\)。也就是如果不計修改，每個數有效取模次數只有 \(O(\log V)\) 次。
對線段樹每個結點記錄區間最大值和區間和。單點修改很好做。區間取模時，如果當前結點最大值 \(<mod\)，就沒必要修改可以直接返回了；如果最大值 \(\ge mod\)，暴力遞歸左右兒子取模，然后 pushup 回來。
復雜度分析。在勢能線段樹的復雜度分析時，我們只需要說明 "暴力遞歸" 的復雜度不會太高即可。因為其他部分和普通線段樹是嚴格 \(O(\log n)\) 的。
對于結點 \(u:[l,r]\)，定義其勢能 \(\phi(u)=\sum_{i=l}^r(\log a_i)\)。
-
當暴力遞歸時，說明 \(u\) 代表的區間內有至少一個數會折半，也就是 \(\log a_i\) 會減少 \(1\)。
所有結點的勢能不增。同時所有包含被取模元素的區間勢能都會減少。
-
單點修改最多只會讓一條鏈上所有線段樹結點的勢能增加 \(\log V\)，也就是總共增加 \(\log n\log V\)。所以最多增加 \(O(q\log n\log V)\)。
-
初始勢能是 \(O(n\log V\log n)\) 的。因為一層勢能是 \(O(n\log V)\) 的，一共 \(\log n\) 層。
綜上所述，每次遞歸總勢能減少 \(1\)，初始勢能 \(O(n\log V\log n)\)，單點修改最多增加 \(O(q\log V\log n)\)，因此總復雜度 \(O((n+q)\log V\log n)\)。
typedef pair<long long, long long> pii;
pii operator+(pii a, pii b) {
return make_pair(a.first + b.first, max(a.second, b.second));
}
pii operator%(pii a, long long b) {
return make_pair(a.first % b, a.second % b);
}
struct SegmentTree {
long long sz;
vector<pair<long long, long long> > val;
pii ide1 = make_pair(0ll, 0ll);
void pushup(long long x) {
val[x] = val[x * 2] + val[x * 2 + 1];
}
void build(long long x, long long lx, long long rx, vector<long long> &a) {
if (lx + 1 == rx) {
val[x] = (lx <= a.size() ? make_pair(a[lx - 1], a[lx - 1]) : ide1);
return ;
}
long long m = (lx + rx) / 2;
build(x * 2, lx, m, a);
build(x * 2 + 1, m, rx, a);
pushup(x);
}
SegmentTree(){}
SegmentTree(vector<long long> &a) {
for (sz = 1; sz < a.size(); sz *= 2);
val.assign(2 * sz, ide1);
build(1, 1, sz + 1, a);
}
void mdf_mod(long long x, long long lx, long long rx, long long l, long long r, long long p) {
// cout << x << ' ' << lx << ' ' << rx << ' ' << l << ' ' << r << ' ' << p << endl;
if (val[x].second < p)
return ;
if (lx + 1 == rx) {
// cout << '!';
val[x] = val[x] % p;
// cout << val[x].first << ' ' << val[x].second << endl;
return ;
}
long long m = (lx + rx) / 2;
if (l < m)
mdf_mod(x * 2, lx, m, l, r, p);
if (r > m)
mdf_mod(x * 2 + 1, m, rx, l, r, p);
pushup(x);
}
void mdf(long long x, long long lx, long long rx, long long p, long long v) {
if (lx + 1 == rx) {
val[x] = make_pair(v, v);
return ;
}
long long m = (lx + rx) / 2;
if (p < m)
mdf(x * 2, lx, m, p, v);
else
mdf(x * 2 + 1, m, rx, p, v);
pushup(x);
}
pii qry(long long x, long long lx, long long rx, long long l, long long r) {
if (l <= lx && rx <= r)
return val[x];
if (l >= rx || lx >= r)
return ide1;
long long m = (lx + rx) / 2;
return qry(x * 2, lx, m, l, r) + qry(x * 2 + 1, m, rx, l, r);
}
} st;
【例二】
題意：
支持三種操作。
-
區間求最大值。
-
單點修改。
-
區間對給定數按位與。
\(n,q\le 4\times 10^5\)，時限 3s.
勢能線段樹最重要的就是想明白什么情況可以剪枝。
顯然，假設我們要對區間與上 \(v\)，如果 \(v\) 中 \(0\) 的位已經全都是 \(0\) 了，可以剪枝。換句話說，設區間的或等于 \(x\)，如果 (x | v) == v 就可以剪枝。
對結點記錄區間 \(\max\) 和區間按位或的值。前兩個正常做，在區間按位與時，如果 (valor[x] | v) == v 就退出。
復雜度分析。
一個結點的勢能定義為 \(\sum_{i=l}^r \operatorname{popcount}(a_i)\)，顯然總勢能 \(O(n\log n\log V)\)，單點修改至多增加 \(O(\log n\log V)\)。
同時每次暴力遞歸總勢能至少 \(-1\)，按位與說明 \(1\) 的個數不增，也就是任何點勢能不會增加。總共 \(O((n+q)\log n\log V)\)。
int n, m;
int a[N];
int mx[N << 2], valor[N << 2];
void pushup(int x) {
mx[x] = max(mx[x * 2], mx[x * 2 + 1]);
valor[x] = valor[x * 2] | valor[x * 2 + 1];
}
void mdf(int x, int lx, int rx, int l, int r, int v) {
if ((v | valor[x]) == v)
return ;
if (l >= rx || lx >= r)
return ;
if (lx + 1 == rx) {
valor[x] &= v;
mx[x] = valor[x];
return ;
}
int m = (lx + rx) / 2;
mdf(x * 2, lx, m, l, r, v);
mdf(x * 2 + 1, m, rx, l, r, v);
pushup(x);
}
void mdf(int x, int lx, int rx, int p, int v) {
if (lx + 1 == rx) {
mx[x] = valor[x] = v;
return ;
}
int m = (lx + rx) / 2;
if (p < m)
mdf(x * 2, lx, m, p, v);
else
mdf(x * 2 + 1, m, rx, p, v);
pushup(x);
}
int qry(int x, int lx, int rx, int l, int r) {
if (l <= lx && rx <= r)
return mx[x];
if (l >= rx || lx >= r)
return -1;
int m = (lx + rx) / 2;
return max(qry(x * 2, lx, m, l, r), qry(x * 2 + 1, m, rx, l, r));
}
void build(int x, int lx, int rx) {
if (lx + 1 == rx) {
mx[x] = valor[x] = a[lx];
return ;
}
int m = (lx + rx) / 2;
build(x * 2, lx, m);
build(x * 2 + 1, m, rx);
pushup(x);
}
【例三】
思路：當整個區間的顏色都相同時，可以直接打懶標記區間加。
對結點 \(u\) 保存：
-
\(clr\)，若 \(clr=0\) 表示區間顏色個數 \(\ge 2\)；否則表示區間顏色都是 \(clr\)。
-
\(tag\)，區間加的懶標記。我們認為 \(tag\) 已經對 \(sum\) 作用了，也就是只作用真子孫。
-
\(sum\)，區間權值和。
復雜度分析。區別在于有區間修改，需要分析會不會有勢能增加。
定義結點 \(u\) 勢能為 \(\phi(u)=[clr_u=0]\)。顯然因為線段樹結點 \(O(n)\) 個，初始勢能是 \(O(n)\) 的。接下來考慮暴力遞歸對勢能的影響。
每次暴力遞歸，說明要修改的區間完全包含 \(u\)，同時 \(u\) 內顏色個數 \(\ge 2\)。考慮所有結點的勢能變化：
-
\(u\) 肯定減少，從 \(\ge 2\) 種顏色變成賦值的顏色。
-
\(u\) 的子孫們勢能不增。因為全部賦值成 \(1\) 種顏色了。
-
非 \(u\) 的祖先、子孫的結點勢能不變，因為在線段樹修改過程中都不會訪問到它們。
-
剩下是 \(u\) 的真祖先。考慮所有 \(u\) 的祖先們，即線段樹在正常拆區間時訪問到的結點。
如果粗略來看，每個被訪問的結點都可能勢能 \(+1\)，線段樹每一層有 \(2\) 個區間被訪問，一共正常訪問 \(O(\log n)\) 個結點，這么說一次操作增加 \(O(\log^2 n)\) 的勢能，總復雜度是 \(O(m\log^3n)\) 嗎？
其實并不是，因為 \(u\) 內的顏色個數都 \(\ge 2\) 了，所以 \(u\) 的祖先顏色個數也 \(\ge 2\)，所以祖先的勢能本就是 \(1\)，不可能增加了，反而可能減少。
綜上所述，暴力遞歸勢能必定減少。而勢能初值為 \(O(n)\) 的，所以復雜度是 \(O((n+m)\log n)\)。
【例四】
題意：
支持三個操作。
-
區間按位與。
-
區間按位或。
-
求區間最大值。
\(n,q\le 2\times 10^5\)，\(a_i<2^{20}\)。
這題麻煩一些，有兩個剪枝：
-
類似例一，對結點記錄
valor, valand，如果發現修改沒用就直接返回。 -
如果修改對于整個區間的作用是一樣的，用懶標記修改。
第一條很好理解，第二條是什么意思呢？
例如我們要與上 11000011，如果 \(u\) 中所有數中間四位都相同（全都是 ??ABCD?? 的形式），相當于區間整體減 ABCD00。或是同理的。
所以我們對結點額外記錄 \(tag\)：區間整體加上 \(tag\) 的懶標記。在我們發現第二條剪枝生效的時候，比如我們要對區間整體 \(+v\)，我們就讓 tag, valor, valand 都 \(+v\)。注意 valor, valand 在這里也是可以加減的，因為我們要么是讓一些 \(1\) 整體變 \(0\)，要么是讓一些 \(0\) 整體變 \(1\)，沒有進位退位的情況。顯然是可以直接放到 valor, valand 身上的。
具體判定：valor ^ valand 中 \(0\) 的位是整個區間都一樣的。
復雜度分析。這題涉及到勢能增加。
把 valor ^ valand 中 \(1\) 的位簡稱為 "有分歧的"。對結點 \(u\) 定義其勢能 \(\phi(u)\) 為 \(u\) 區間有分歧的位數。初始總勢能是 \(O(n\log V)\) 的。
首先強行遞歸肯定會使得 \(\phi(u)\) 至少減一。然后對于每個正常訪問到的結點，勢能最多增加 \(O(\log V)\)，所以一次操作勢能增加量為 \(O(\log n\log V)\)。總增加 \(O(q\log n\log V)\)。
因此總復雜度是 \(O(q\log n\log V)\) 的。
void tagadd(int u, int v){
tagAnd[u] += v; tagOr[u] += v; mx[u] += v; lazy[u] += v;
}
void pushUp(int i){
tagAnd[i] = tagAnd[lc] & tagAnd[rc];
tagOr[i] = tagOr[lc] | tagOr[rc];
mx[i] = max(mx[lc], mx[rc]);
}
void pushDown(int i){
tagadd(lc, lazy[i]);
tagadd(rc, lazy[i]);
lazy[i] = 0;
}
void rangeAnd(int i,int L,int R,int l,int r,int x){
if ((tagOr[i] & x) == tagOr[i]) return;
int check = tagAnd[i]^tagOr[i]; // check 表示相等的位置。
if (l <= L && r >= R && ((check | x) == x)) // x中為0的地方，check也為0.
tagadd(i, (tagAnd[i]&x)-tagAnd[i]);
else{
int mid=(L+R)>>1;
pushDown(i);
if(l<=mid) rangeAnd(lc,L,mid,l,r,x);
if(r>mid) rangeAnd(rc,mid+1,R,l,r,x);
pushUp(i);
}
}
void rangeOr(int i,int L,int R,int l,int r,int x){
if ((tagAnd[i] | x) == tagAnd[i]) return;
int check = tagAnd[i]^tagOr[i]; // check 表示相等的位置。
if (l <= L && r >= R && ((check & x) == 0)) // x中為1的地方，check也為0.
tagadd(i, (tagAnd[i]|x)-tagAnd[i]);
else{
int mid=(L+R)>>1;
pushDown(i);
if(l<=mid) rangeOr(lc,L,mid,l,r,x);
if(r>mid) rangeOr(rc,mid+1,R,l,r,x);
pushUp(i);
}
}
int queryMax(int i,int L,int R,int l,int r){
if(l<=L&&r>=R) return mx[i];
int mid=(L+R)>>1,res=-1;
pushDown(i);
if(l<=mid) res=max(res,queryMax(lc,L,mid,l,r));
if(r>mid) res=max(res,queryMax(rc,mid+1,R,l,r));
return res;
}
void build(int i,int L,int R){
if(L==R){
int a; scanf("%d", &a);
mx[i] = tagAnd[i] = tagOr[i] = a; lazy[i]=0;
}
else{
int mid=(L+R)>>1;
build(lc,L,mid); build(rc,mid+1,R);
pushUp(i);
}
}
【例五】
支持三個操作。
-
區間求和。
-
區間加。
-
區間開方下取整。
\(n,m,a_i\le 10^5\)。
考慮怎么剪枝。記錄區間 \(mn\) 和 \(mx\)。
-
若 \(mn=mx\)，等價于區間減法。
-
若 \(mn+1=mx\)，則要么等價于區間減法，要么等價于區間賦值。
對于 \(mx-mn>1\) 就暴力遞歸。
復雜度分析。這題的勢能分析采用對數的形式，是個勢能分析的 trick。
這里的定義比較特別。記 \(\phi(u)=\log(mx-mn)\)（若 \(mx-mn\) 則 \(\phi(u)=0\)）。
-
分析區間開方。
如果暴力遞歸了，說明 \(mx-mn\ge 2\)。我們在這個條件下求證 \(u\) 勢能至少 \(-1\)。
設 \([\sqrt{mn}]=C,[\sqrt{mx}]=C+\Delta\)。轉證 \(mx-mn\ge 2\Delta\)。
\[ \begin{aligned} mx-mn-2\Delta&\ge (C+\Delta)^2-((C+1)^2-1)-2\Delta\\ &= 2C\Delta+\Delta^2-2C-2\Delta\\ &=\Delta(2C+\Delta)-2(C+\Delta) \end{aligned} \]當 \(\Delta \ge 2\) 時，顯然成立。而當 \(\Delta=0/1\) 時，\(\phi(u')=0\) 顯然變小了。
浙公網安備 33010602011771號