终于学会线段树了！！！
这篇博客将简单介绍 atcoder::lazy_segtree 的使用方法。
构造
lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> a);
下面所有代码将用 \(01\) 序列，区间 \(\operatorname{XOR} 1\) 区间求和举例。
- 线段树节点 \(S\)：每个节点维护的信息。
上面的题目要求每个节点维护区间和以及区间长度。
struct S{int sum,len;};
- 函数
S op(S x,S y)：push_up函数。
即合并两个线段树节点。
区间和和区间长度都是直接相加。
S op(S l,S r){return S{l.sum + r.sum,l.len + r.len};}
- 函数
S e()：返回初始值 \(e\)。
它要求任意元素 \(x\) 和 \(e\) 操作后返回值是 \(x\)，例如取 \(\min\) 时 \(e = \inf\)，本题中 \(e = \{0,0\}\)。
S e(){return S{0,0};}
- 操作 \(F\)：修改时进行的操作。
本题中 \(F =0/1\) 表示区间要异或的值。
using F = bool;
- 函数
S mapping(F f,S x)：返回元素 \(x\) 应用 \(f\) 操作后的值。
在本题里，异或 \(1\) 后 \(sum = len-sum\)，异或 \(0\) 则不变。
S mapping(F f,S x){return S{(f ? x.len - x.sum : x.sum),x.len};}
- 函数
F composition(F f,F g)：操作之间的复合，返回 \(f(g(x))\)。
也就是两个 \(tag\) 的合并。在本题里，合并两个异或 \(tag\) 即把它们异或起来。
F composition(F f,F g){return (F)(f ^ g);}
- 函数
F id()：该函数应有 \(f(x) = x\)。
本题中返回 \(0\) 即可。
F id(){return 0;}
完整代码
using namespace atcoder;
int T,n;
struct S{int sum,len;};
using F = bool;
S op(S l,S r){return S{l.sum + r.sum,l.len + r.len};}
S e(){return S{0,0};}
S mapping(F f,S x){return S{(f ? x.len - x.sum : x.sum),x.len};}
F composition(F f,F g){return (F)(f ^ g);}
F id(){return 0;}
vector<S> a; int q;
void los(){
cin >> n >> q; string s;
cin >> s,s = " " + s;
for(int i = 1;i <= n;i ++) a.push_back(S{s[i] - '0',1});
lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
while(q --){
int po,l,r;
if(cin >> po >> l >> r,!po) seg.apply(l - 1,r,F(1));
else cout << seg.prod(l - 1,r).sum << "\n";
}
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}
最近做的线段树题都会使用 atcoder::lazy_segtree，写完以后会把题目和代码贴在这里。
P2574 XOR的艺术
\(01\) 序列 \(a\)，支持区间异或 \(1\)，区间求和。
就是上面的例题。
ACLPC L - Lazy Segment Tree
\(01\) 序列 \(a\)，支持区间异或 \(1\)，区间求逆序对。
注意到 \(01\) 序列的逆序对只能是子序列 \(10\) 的数量，线段树维护区间 \(0,1,10\) 的数量。
using namespace atcoder;
const int N = 5e5+5;
using namespace std;
int T,n,q,tmp,po,l,r;
struct S{int x,y; ll ans;};
using F = bool;
S op(S l,S r){return S{l.x + r.x,l.y + r.y,l.ans + r.ans + 1ll * l.y * r.x};}
S e(){return S{0,0,0};}
S mapping(F f,S x){return !f ? x : S{x.y,x.x,1ll * x.x * x.y - x.ans};}
F composition(F f,F g){return F(f ^ g);}
F id(){return 0;}
vector<S> a;
void los(){
cin >> n >> q;
for(int i = 1;i <= n;i ++) cin >> tmp,a.emplace_back(!tmp,tmp,0);
lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
while(q --){
if(cin >> po >> l >> r,po == 1) seg.apply(l - 1,r,F(1));
else cout << seg.prod(l - 1,r).ans << "\n";
}
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}
[ABC265G] 012 Inversion
给定 \(012\) 序列 \(a\)，支持区间替换（\(0 \to x,1 \to y,2 \to z,x,y,z \in \{0,1,2\}\)）和区间查逆序对。
比较恶心的题。
线段树节点记录 \(0,1,2,10,20,21\) 的数量，tag 维护 \(0,1,2\) 分别变成谁。修改时，\(0,1,2\) 的数量可以直接得到，原本的 \(10,20,21\) 直接贡献给 \(f_1f_0,f_2f_0,f_2f_1\)，注意 \(01\) 也会贡献给 \(f_0f_1\)。\(01\) 的数量显然是原本的 \(0 \times 1 - 01\)。
合并两个 tag \(f,g\) 时，只需要返回 \(f_{g_i}\)。
#include <atcoder/lazysegtree>
using namespace atcoder;
struct S{
ll r[6];
ll operator [](int x){return r[x];};
};
struct F{
int f[3];
int operator [](int x){return f[x];};
};
S op(S l,S r){
return S{{l[0] + r[0],l[1] + r[1],l[2] + r[2],
l[3] + r[3] + l[1] * r[0],l[4] + r[4] + l[2] * r[0],l[5] + r[5] + l[2] * r[1]}};
}S e(){return S{0,0,0,0,0,0};}
S mapping(F f,S x){
vector<vector<ll>> fk(3,vector<ll>(3)); vector<ll> sb(3);
fk[f[0]][f[0]] += x[0],fk[f[1]][f[1]] += x[1],fk[f[2]][f[2]] += x[2],
fk[f[1]][f[0]] += x[3],fk[f[2]][f[0]] += x[4],fk[f[2]][f[1]] += x[5],
fk[f[0]][f[1]] += x[0] * x[1] - x[3],fk[f[0]][f[2]] += x[0] * x[2] - x[4],
fk[f[1]][f[2]] += x[1] * x[2] - x[5],sb[f[0]] += x[0],sb[f[1]] += x[1],sb[f[2]] += x[2];
return S{sb[0],sb[1],sb[2],fk[1][0],fk[2][0],fk[2][1]};
}F composition(F f,F g){
return F{f[g[0]],f[g[1]],f[g[2]]};
}F id(){return {0,1,2};}
int T,n,q,x,po,l,r,s1,s2,s3;
vector<S> a;
void los(){
cin >> n >> q;
for(int i = 1;i <= n;i ++) cin >> x,a.push_back({(x == 0),(x == 1),(x == 2),0,0,0});
lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
while(q --){
if(cin >> po >> l >> r,po == 1){
auto s = seg.prod(l - 1,r);
cout << s.r[3] + s.r[4] + s.r[5] << "\n";
}else cin >> s1 >> s2 >> s3,seg.apply(l - 1,r,F{s1,s2,s3});
}
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}