线段树 & 平衡树
用线段树/平衡树维护的序列问题可以分为两类：
1.静态型：维护一个类似于 \(\sum_{l,r}....\) 的值，或者是多次询问区间或全局的一些特征值。
2.动态型：支持动态修改和动态询问区间信息的类型。
对于静态型，我们通常首先思考怎样求单个区间的答案值，同理，动态型通常先考虑不带修，也就是一个序列怎么做。
对于一个难以维护的题目，我们可以先写出要维护的信息，然后画出一个信息和另一个的依赖推导关系，最后得到闭包求出答案。
例如：
这题可以转化为：求区间内任意三元组 \((i,j,k)(i < j < k)\) 的 \(A_i - B_j + A_k\) 最大值。
考虑静态问题，观察能不能计算跨过分治中心的答案，架构序列分治的模型。我们发现有四种情况：
考虑 \(i,j,k\) 全在左右边，就是左右边单独的答案 \(\max\) 。考虑 \(i,j\) 在左边的情况：
首先由于 \(k\) 一定在右边，取 \(\max a_k\) 一定是最优的。所以左边要求 \(a_i - b_j\) 的最大值。
考虑左边的区间，同样地，我们发现， \(a_i - b_j\) 要么就是左边儿子的答案，要么就是右边儿子的答案，要么就是左边 \(\max a_i\) 减去右边 \(\min b_j\) ，这样我们将问题转化为了求 \(a,b\) 的最值，成功解决。
其他情况同样讨论即可。
按照上面的说法，这张图画下来就应该是这样的：
展开到最后一步，理清思路，再返回实现代码，很快就可以做完。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5,inf = 0x3f3f3f3f;
int n,m,A[N],B[N];
struct Node{
int mxa,mnb,ansij,ansjk,ans;
};
Node operator +(Node x,Node y)
{
Node z;
z.mxa = max(x.mxa,y.mxa);
z.mnb = min(x.mnb,y.mnb);
z.ansij = max(max(x.ansij,y.ansij),x.mxa - y.mnb);
z.ansjk = max(max(x.ansjk,y.ansjk),y.mxa - x.mnb);
z.ans = max(max(x.ans,y.ans),max(x.ansij + y.mxa,x.mxa + y.ansjk));
return z;
}
struct Segment_Tree{
Node a[N << 2];
inline void pushup(int pos) {a[pos] = a[pos << 1] + a[pos << 1 | 1];}
inline void modify(int l,int r,int x,int k,int type,int pos)
{
if(l == r) {if(type == 1) a[pos].mxa = k; else a[pos].mnb = k; return;}
int mid = (l + r) >> 1;
if(x <= mid) modify(l,mid,x,k,type,pos << 1);
else modify(mid + 1,r,x,k,type,pos << 1 | 1);
pushup(pos);
}
inline Node query(int l,int r,int L,int R,int pos)
{
if(L <= l && r <= R) return a[pos];
int mid = (l + r) >> 1; Node ret = {-inf,-inf,-inf,-inf,-inf};
if(L <= mid) ret = query(l,mid,L,R,pos << 1);
if(R > mid) {if(ret.mxa == -inf) ret = query(mid + 1,r,L,R,pos << 1 | 1); else ret = ret + query(mid + 1,r,L,R,pos << 1 | 1);}
return ret;
}
inline void build(int l,int r,int pos)
{
if(l == r) {a[pos].mxa = A[l]; a[pos].mnb = B[l]; a[pos].ansij = a[pos].ansjk = a[pos].ans = -inf; return;}
int mid = (l + r) >> 1;
build(l,mid,pos << 1); build(mid + 1,r,pos << 1 | 1);
pushup(pos);
}
}t;
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++) cin>>A[i];
for(int i = 1;i <= n;i++) cin>>B[i];
t.build(1,n,1);
Node ret = t.query(1,n,1,n,1);
for(int i = 1,op,x,y;i <= m;i++)
{
cin>>op>>x>>y;
if(op == 1 || op == 2) t.modify(1,n,x,y,op,1);
else cout<<t.query(1,n,x,y,1).ans<< '\n';
}
return 0;
}
技巧
[HNOI2011] 括号修复 / [JSOI2011]括号序列
按照套路，首先考虑静态怎么做，发现可以转化：
尽量匹配所有的括号，删掉，剩下的一定形如 ))))))...((((((
所以我们只需要改成 ()()()()()()()()()()()()...
假设剩右括号有 \(p\) 个，左括号有 \(q\) 个，我们可以发现答案就是 \(\lceil \frac p2 \rceil + \lceil \frac q2 \rceil\) 。
解决了静态序列的问题，容易看出来这个东西是好合并的，讨论一下即可。
分开考虑维护几个操作：
1.Replace
区间推平，线段树上用一个标记即可，推平后整个区间的值可以 \(\Theta(1)\) 计算。
2.Swap
翻转串，这里意识到需要用平衡树，平衡树上 tag 照样可以维护第一个，所以套文艺平衡树即可，再用一个 tag。
3.Invert
取反，这个很不好做，先前再 Flower's Land 当中见过类似套路，观察到取反再取反就不变，状态数 \(\Theta(1)\) 个，我们同时维护 \(2\) 种状态的答案，取反时打标记再交换答案即可。
这样我们就用平衡树维护了操作，可以回答询问。但是笔者仍然调了两个小时，最后发现，问题出在 Swap 上，线段树区间操作的两大要求就是 懒标记的可并性 和 当前区间被整个包含时 \(\Theta(1)\) 得出答案 。就是说翻转后的区间答案不一样，我们要求 \(\Theta(1)\) 算出，怎么办呢？
发现翻转这个东西也是只有 \(2\) 个状态的操作，所以我们再同时维护出翻转前后的答案即可。
这样，我们用 \(3\) 个标记，\(4\) 个状态大常数 \(\Theta(n \log n)\) 地维护出了信息。
注意标记顺序要将 Invert 放在第一位，并且取反后要将推平标记也取反。推平后要将取反标记归零。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n,q,a[N];
char s[N];
struct fhq{//正/反，换/不换
int val[2][N],valpre[2][2][N],valsuf[2][2][N],tot = 0,lc[N],rc[N],hp[N],siz[N],tagflip[N],tagrev[N],tagcov[N],root = 0,y,z,w,p;
inline void pushup(int pos)
{
valpre[0][0][pos] = valpre[0][0][lc[pos]] + max(0,valpre[0][0][rc[pos]] + (val[0][pos] == 1 ? 1 : -1) - valsuf[0][0][lc[pos]]);
valsuf[0][0][pos] = valsuf[0][0][rc[pos]] + max(0,valsuf[0][0][lc[pos]] + (val[0][pos] == 0 ? 1 : -1) - valpre[0][0][rc[pos]]);
valpre[0][1][pos] = valpre[0][1][lc[pos]] + max(0,valpre[0][1][rc[pos]] + (val[1][pos] == 1 ? 1 : -1) - valsuf[0][1][lc[pos]]);
valsuf[0][1][pos] = valsuf[0][1][rc[pos]] + max(0,valsuf[0][1][lc[pos]] + (val[1][pos] == 0 ? 1 : -1) - valpre[0][1][rc[pos]]);
swap(lc[pos],rc[pos]);
valpre[1][0][pos] = valpre[1][0][lc[pos]] + max(0,valpre[1][0][rc[pos]] + (val[0][pos] == 1 ? 1 : -1) - valsuf[1][0][lc[pos]]);
valsuf[1][0][pos] = valsuf[1][0][rc[pos]] + max(0,valsuf[1][0][lc[pos]] + (val[0][pos] == 0 ? 1 : -1) - valpre[1][0][rc[pos]]);
valpre[1][1][pos] = valpre[1][1][lc[pos]] + max(0,valpre[1][1][rc[pos]] + (val[1][pos] == 1 ? 1 : -1) - valsuf[1][1][lc[pos]]);
valsuf[1][1][pos] = valsuf[1][1][rc[pos]] + max(0,valsuf[1][1][lc[pos]] + (val[1][pos] == 0 ? 1 : -1) - valpre[1][1][rc[pos]]);
swap(lc[pos],rc[pos]);
siz[pos] = siz[lc[pos]] + siz[rc[pos]] + 1;
}
inline void change_flip(int pos)
{
if(!pos) return;
swap(val[0][pos],val[1][pos]);
swap(valpre[0][0][pos],valpre[0][1][pos]); swap(valsuf[0][0][pos],valsuf[0][1][pos]);
swap(valpre[1][0][pos],valpre[1][1][pos]); swap(valsuf[1][0][pos],valsuf[1][1][pos]);
tagflip[pos] ^= 1;
if(tagcov[pos] != -1) tagcov[pos] ^= 1;
}
inline void change_rev(int pos)
{
if(!pos) return;
swap(lc[pos],rc[pos]);
swap(valpre[0][0][pos],valpre[1][0][pos]); swap(valpre[0][1][pos],valpre[1][1][pos]);
swap(valsuf[0][0][pos],valsuf[1][0][pos]); swap(valsuf[0][1][pos],valsuf[1][1][pos]);
tagrev[pos] ^= 1;
}
inline void change_cov(int pos,int x)
{
if(!pos) return;
val[0][pos] = x; val[1][pos] = x ^ 1;
if(x == 0)
{
valpre[0][0][pos] = 0; valsuf[0][0][pos] = siz[pos];
valpre[0][1][pos] = siz[pos]; valsuf[0][1][pos] = 0;
valpre[1][0][pos] = 0; valsuf[1][0][pos] = siz[pos];
valpre[1][1][pos] = siz[pos]; valsuf[1][1][pos] = 0;
}
else
{
valpre[0][0][pos] = siz[pos]; valsuf[0][0][pos] = 0;
valpre[0][1][pos] = 0; valsuf[0][1][pos] = siz[pos];
valpre[1][0][pos] = siz[pos]; valsuf[1][0][pos] = 0;
valpre[1][1][pos] = 0; valsuf[1][1][pos] = siz[pos];
}
tagcov[pos] = x; tagflip[pos] = 0;
}
inline void pushdown(int pos)
{
if(tagflip[pos])
{
change_flip(lc[pos]); change_flip(rc[pos]);
tagflip[pos] = 0;
}
if(tagrev[pos])
{
change_rev(lc[pos]); change_rev(rc[pos]);
tagrev[pos] = 0;
}
if(tagcov[pos] != -1)
{
change_cov(lc[pos],tagcov[pos]); change_cov(rc[pos],tagcov[pos]);
tagcov[pos] = -1;
}
}
inline void split(int &x,int &y,int k,int pos)
{
if(!pos) {x = y = 0; return;}
pushdown(pos);
if(siz[lc[pos]] + 1 <= k) x = pos,split(rc[x],y,k - siz[lc[pos]] - 1,rc[pos]);
else y = pos,split(x,lc[y],k,lc[pos]);
pushup(pos);
}
inline int merge(int x,int y)
{
pushdown(x); pushdown(y);
if(!x || !y) return x + y;
if(hp[x] < hp[y])
{
rc[x] = merge(rc[x],y);
pushup(x);
return x;
}
else
{
lc[y] = merge(x,lc[y]);
pushup(y);
return y;
}
}
inline int new_node(int x)
{
++tot;
val[0][tot] = x; val[1][tot] = x ^ 1;
valpre[0][0][tot] = x; valsuf[0][0][tot] = x ^ 1;
valpre[0][1][tot] = x ^ 1; valsuf[0][1][tot] = x;
valpre[1][0][tot] = x; valsuf[1][0][tot] = x ^ 1;
valpre[1][1][tot] = x ^ 1; valsuf[1][1][tot] = x;
lc[tot] = rc[tot] = 0;
siz[tot] = 1;
hp[tot] = 1ll * rand() * rand();
return tot;
}
inline void ist(int x)
{
root = merge(root,new_node(x));
}
inline void cover(int l,int r,int x)
{
split(y,z,l - 1,root);
split(w,p,r - l + 1,z);
change_cov(w,x);
root = merge(y,merge(w,p));
}
inline void reverse(int l,int r)
{
split(y,z,l - 1,root);
split(w,p,r - l + 1,z);
change_rev(w);
root = merge(y,merge(w,p));
}
inline void flip(int l,int r)
{
split(y,z,l - 1,root);
split(w,p,r - l + 1,z);
change_flip(w);
root = merge(y,merge(w,p));
}
inline int query(int l,int r)
{
split(y,z,l - 1,root);
split(w,p,r - l + 1,z);
int nowp = valpre[0][0][w],nows = valsuf[0][0][w];
root = merge(y,merge(w,p));
return (nowp + 1) / 2 + (nows + 1) / 2;
}
}t;
int main()
{
fill(t.tagcov,t.tagcov + N,-1);
srand(time(NULL));
cin>>n>>q;
scanf("%s",s + 1);
for(int i = 1;i <= n;i++) a[i] = (s[i] == '(') ? 0 : 1;
for(int i = 1;i <= n;i++) t.ist(a[i]);
string op; char d; int x,y;
for(int i = 1;i <= q;i++)
{
cin>>op;
if(op == "Replace")
{
cin>>x>>y>>d;
t.cover(x,y,(d == ')') ? 1 : 0);
}
else if(op == "Swap")
{
cin>>x>>y;
t.reverse(x,y);
}
else if(op == "Invert")
{
cin>>x>>y;
t.flip(x,y);
}
else if(op == "Query")
{
cin>>x>>y;
cout<<t.query(x,y)<< '\n';
}
}
return 0;
}