rt，学习线段树也学了不少维护信息的方法，记录一下防止遗忘。
P3870 [TJOI2009] 开关/P5057 [CQOI2006] 简单题
由于序列是 01 串，所以区间和就是区间 \(1\) 的个数，每次反转只需把结点值赋为 \(r-l+1-v\) 即可。另外反转偶数次相当于未反转，因此反转 tag 可以每次 \(+1\bmod 2\)。
P1438 无聊的数列
注意到表述等差序列中的每一个数只需要知道首项 \(k\)、公差 \(d\)、和每一个数的下标 \(i\)，因此 tag 维护这三个值即可。同时由于打 tag 的时候一定知道这个 tag 所管辖的区间左端点的下标，因此可以把下标省略，将值补到首项上。
pushdown 操作代码：
inline void pushdown(int p,int l,int r) {
int mid = (l + r) >> 1,k = tag[p].k,d = tag[p].d;
tr[p<<1] += (k+k+d*(mid-l))*(mid-l+1)/2;
tr[p<<1|1] += (k+d*(mid-l+1)+k+d*(r-l))*(r-mid)/2;
tag[p<<1].d += d;
tag[p<<1|1].d += d;
tag[p<<1].k += k;
tag[p<<1|1].k += k+d*(mid-l+1);
tag[p].d = tag[p].k = 0;
}
P1253 扶苏的问题
赋值优先级大于加法。
pushdown 操作：
inline void pushdown(int p,int l,int r) {
if (tagm[p] != MIN) {
t[p<<1] = t[p<<1|1] = tagm[p];
tagm[p<<1] = tagm[p<<1|1] = tagm[p];
tagp[p<<1] = tagp[p<<1|1] = 0;
}
t[p<<1] += tagp[p];
t[p<<1|1] += tagp[p];
tagp[p<<1] += tagp[p];
tagp[p<<1|1] += tagp[p];
tagm[p] = MIN,tagp[p] = 0;
}
P2572 [SCOI2010]序列操作
一句话：最长连续 \(1\) 的个数有 \(3\) 个状态转移而来：左子树最长连续 \(1\)，右子树最长连续 \(1\)，左子树右端最长连续 \(1\) 和右子树左端最长连续 \(1\)。
巨大细节，尤其锻炼代码能力。需要注意的细节包括但不限于：pushdown 优先级、如何维护左右连续 \(1\)、如何查询……
P3722 [AH2017/HNOI2017] 影魔
对于目前的我还是过于超标了……以后补。
P6327 区间加区间 sin 和
和差角公式：
\[\sin(a+b) = \sin a\cos b+\cos a\sin b \]\[\cos(a+b) = \cos a\cos b-\sin a\sin b \]我们每个节点可以维护这一段区间的 \(\sin\) 和，由上可以推得：
\[\begin{aligned} \sin(a+c) +\sin(b+c) &= \sin a\cos c+\cos a\sin c +\sin b\cos c +\cos b\sin c \\ &= \sin c(\cos a+\cos b) + \cos c(\sin a+\sin b) \end{aligned} \]因此我们可以直接由区间 \(\sin\) 和与区间 \(\cos\) 和更新数值。
P2824 [HEOI2016/TJOI2016] 排序
由于只有最后一次询问，我们考虑离线做法。（本题有复杂度更优的在线做法，但是比较难）
首先我们需要对 01 串做一个研究：我们发现，借助线段树，给一个 01 串排序是 \(O(\log n)\) 的复杂度。做法：查询区间和（\(1\) 的个数）\(cnt\)，然后将 \([l,r-cnt]\) 赋值为 \(0\)，将\([r-cnt+1,r]\) 赋值为 \(1\)。
然后看此题，因为我们最后访问的只是一个位置，且序列是一个 \(1 \sim n\) 的排列，因此考虑二分答案。因为我们只关心第 \(q\) 位置上的数是否大于等于我们二分的 \(mid\)，因此序列可以转化为 01 串。
然后我们对每个 \(mid\) 建树，把大于等于 \(mid\) 的赋值为 \(1\)，小于 \(mid\) 的赋值为 \(0\)，每次排序就是对 01 串排序，最后看第 \(q\) 位是不是 \(1\)。
最终的时间复杂度为 \(O(n\log^2 n)\)。
P4145 上帝造题的七分钟 2 / 花神游历各国
一句话：由于 \(10^{12}\) 开方 \(6\) 次就变成了 \(1\)，所以直接暴力单点修改，当区间和与区间长度相同时直接回溯。
因为很难想到 \(\sqrt{a+c}+\sqrt{b+c}\) 如何由 \(\sqrt{a}+\sqrt{b}\) 推来，因此只能直接暴力维护。但是注意到每个数最多开方 \(6\) 次，所以可以直接跳过区间长度等于区间和（即每个区间都是 \(1\)）的区间。
P7497 四方喝彩
难写的抽象题。
注意到和模板 \(2\) 的区别仅有操作 \(3\)，因此我们只需考虑操作 \(3\)。
然后很容易想到假做法 \(1\)：
对每一个结点维护一个解锁时间，如果到了解锁时间就修改，否则不改。错因：如果封锁了父亲节点，修改了孩子节点，由于孩子节点没有修改时间，因此造成误修改。
接着就是我想到的假做法 \(2\)：
既然我们是因为孩子不知道修改时间错误的，那我们就把修改时间当成懒标记一样往下推不行么，同时我们想到把封锁和解封拆成两个操作，结果发现过不了样例 \(2\)。错因：当封锁区间重叠时，我们先解封了一部分，就会导致我们维护的“区间被封锁的元素个数”被干扰，造成误修改。
因此最终的正解：
不要把封锁状态当成 \(0\) 或 \(1\)，而是记录结点叠加的封锁次数。注意如果当前结点被封锁，那么不能对这个结点进行加、乘操作。同时如果在下传懒标记时有一个孩子被封锁，不能修改这个孩子。同时把区间和拆成被封锁的区间和与非被封锁的区间和。上传标记也要判断当前节点是否被封锁，若被封锁则不要由孩子更新（因为孩子可能还没来得及更新封锁后的值）。
总之，代码：
#include <bits/stdc++.h>
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int maxn = 2e5+6;
const int mod = 1e9+7;
int n,m;
struct node{
int up,lp,lc,cnt;//up 区间未被封锁的数字的和，p 区间被封锁的数字的和，lc 区间被封锁的数字个数，cnt 区间被封锁次数。
int tagt,tagp;
node(){
up = lp = lc = cnt = tagp = 0;
tagt = 1;
}
}t[maxn<<2];
int a[maxn];
inline void pushup(int p) {
if (t[p].cnt == 0) {
t[p].up = (t[ls].up % mod + t[rs].up % mod) % mod;
t[p].lp = (t[ls].lp % mod + t[rs].lp % mod) % mod;
t[p].lc = t[ls].lc + t[rs].lc;
}
}
inline void pushdown(int p,int l,int r) {
if (l == r) return;
if (t[p].tagp == 0 && t[p].tagt == 1) return;
if (t[p].cnt > 0) return;
int mid = (l + r) >> 1;
if (t[ls].cnt == 0) {
t[ls].tagt = t[p].tagt*t[ls].tagt%mod;
t[ls].tagp = (t[p].tagt*t[ls].tagp%mod+t[p].tagp%mod)%mod;
t[ls].up = (t[ls].up%mod*t[p].tagt%mod+t[p].tagp%mod*(mid-l+1-t[ls].lc)%mod)%mod;
}
if (t[rs].cnt == 0) {
t[rs].tagt = t[p].tagt*t[rs].tagt%mod;
t[rs].tagp = (t[p].tagt*t[rs].tagp%mod+t[p].tagp%mod)%mod;
t[rs].up = (t[rs].up%mod*t[p].tagt%mod+t[p].tagp%mod*(r-mid-t[rs].lc)%mod)%mod;
}
t[p].tagt = 1,t[p].tagp = 0;
}
void build(int p,int l,int r) {
t[p].tagt = 1;
if (l == r) {
t[p].up = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void modify(int p,int v,int l,int r,int s,int e,int tp) {
if (t[p].cnt > 0) return;
if (l <= s && e <= r) {
if (tp == 1) {
t[p].up = ((e-s+1-t[p].lc)*v%mod+t[p].up)%mod;
t[p].tagp = (t[p].tagp%mod+v%mod)%mod;
}
if (tp == 2) {
t[p].up = (v%mod*t[p].up%mod)%mod;
t[p].tagp = (t[p].tagp%mod*v%mod)%mod;
t[p].tagt = (t[p].tagt%mod*v%mod)%mod;
}
return;
}
int mid = (s + e) >> 1;
pushdown(p,s,e);
if (l <= mid) modify(ls,v,l,r,s,mid,tp);
if (r > mid) modify(rs,v,l,r,mid+1,e,tp);
pushup(p);
}
void lock(int p,int l,int r,int s,int e) {
if (l <= s && e <= r) {
pushdown(p,s,e);
if (t[p].cnt == 0) {
t[p].lp = (t[p].lp+t[p].up)%mod;
t[p].lc = e-s+1;
t[p].up = 0;
}
++t[p].cnt;
return;
}
int mid = (s + e) >> 1;
pushdown(p,s,e);
if (l <= mid) lock(ls,l,r,s,mid);
if (r > mid) lock(rs,l,r,mid+1,e);
pushup(p);
}
void unlock(int p,int l,int r,int s,int e) {
if (l <= s && e <= r) {
--t[p].cnt;
if (t[p].cnt == 0) {
if (s == e) swap(t[p].up,t[p].lp),t[p].lc = 0;
else pushup(p);
}
return;
}
int mid = (s + e) >> 1;
pushdown(p,s,e);
if (l <= mid) unlock(ls,l,r,s,mid);
if (r > mid) unlock(rs,l,r,mid+1,e);
pushup(p);
}
int query(int p,int l,int r,int s,int e) {
if (l <= s && e <= r) {
return (t[p].up+t[p].lp)%mod;
}
int mid = (s + e) >> 1;
pushdown(p,s,e);
int ret = 0;
if (l <= mid) ret = (ret + query(ls,l,r,s,mid)%mod) %mod;
if (r > mid) ret = (ret + query(rs,l,r,mid+1,e)%mod) %mod;
return ret;
}
struct Lock{
int l,r,t;
bool operator < (const Lock &a) const{
return t > a.t;
}
};
priority_queue<Lock> q;
signed main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1,1,n);
int l,r,op,x;
for (int i = 1; i <= m; i++) {
cin >> op >> l >> r;
if (op == 1) {
cin >> x;
modify(1,x,l,r,1,n,1);
}
if (op == 2) {
cin >> x;
modify(1,x,l,r,1,n,2);
}
if (op == 3) {
cin >> x;
lock(1,l,r,1,n);
q.push({l,r,i+x});
}
if (op == 4) {
cout << query(1,l,r,1,n) % mod << '\n';
}
while (!q.empty()&&q.top().t == i) {
unlock(1,q.top().l,q.top().r,1,n);
q.pop();
}
}
return 0;
}
CF620E New Year Tree
一句话：用 dfs 序把树转为线性结构，用两个数组分别表示进序列和出序列的时间，改每一个根节点等价于改 dfs 序列中进和出之间的所有点，颜色个数不多，可以借助状态压缩。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 4e5+6;
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],tot;
inline void add(int u,int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int n,m,cnt;
int c[maxn];
int f[maxn],l[maxn],pos[maxn];
void dfs(int p,int fa) {
pos[++cnt] = p;
f[p] = cnt;
for (int i = head[p]; i; i = e[i].nxt) {
if (e[i].to == fa) continue;
dfs(e[i].to,p);
}
l[p] = cnt;
}
struct node{
int v,tag;
}t[maxn<<2];
inline void pushup(int p) {
t[p].v = t[p<<1].v | t[p<<1|1].v;
}
inline void pushdown(int p) {
t[p<<1].tag = t[p<<1|1].tag = t[p].tag;
t[p<<1].v = 1ll<<(t[p].tag);
t[p<<1|1].v = 1ll<<(t[p].tag);
t[p].tag = -1;
}
void build(int p,int l,int r) {
t[p].tag = -1;
if (l == r) {
t[p].v = 1ll<<(c[pos[l]]);
return;
}
int mid = (l + r) >> 1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,int v,int l,int r,int s,int e) {
if (l <= s && e <= r) {
t[p].v = 1ll<<v;
t[p].tag = v;
return;
}
int mid = (s + e) >> 1;
if (s != e && t[p].tag != -1) pushdown(p);
if (l <= mid) modify(p<<1,v,l,r,s,mid);
if (r > mid) modify(p<<1|1,v,l,r,mid+1,e);
pushup(p);
}
int query(int p,int l,int r,int s,int e) {
if (l <= s && e <= r) {
return t[p].v;
}
int mid = (s + e) >> 1;
if (s != e && t[p].tag != -1) pushdown(p);
int ret = 0;
if (l <= mid) ret |= query(p<<1,l,r,s,mid);
if (r > mid ) ret |= query(p<<1|1,l,r,mid+1,e);
return ret;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
for (int i = 1; i <= n - 1; i++) {
int x,y;
cin >> x >> y;
add(x,y);
add(y,x);
}
dfs(1,0);
build(1,1,n);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int u,co;
cin >> u >> co;
modify(1,co,f[u],l[u],1,n);
}else{
int u;
cin >> u;
cout << __builtin_popcountll(query(1,f[u],l[u],1,n)) << '\n';
}
}
return 0;
}