大意: 给定括号序列, 每次询问交换两个括号, 求括号树的直径.
用[ZJOI2007]捉迷藏的方法维护即可.
#include <iostream> #include <algorithm> #include <cstdio> #include <queue> #define REP(i,a,n) for(int i=a;i<=n;++i) #define pb push_back #define lc (o<<1) #define rc (lc|1) #define mid ((l+r)>>1) #define ls lc,l,mid #define rs rc,mid+1,r using namespace std; const int N = 3e5+10, INF = 0x3f3f3f3f; int n, m; char s[N]; struct _ { int l,r,dis,l_plus,l_minus,r_plus,r_minus; _ (int l=0,int r=0,int dis=0,int l_plus=0,int l_minus=0,int r_plus=0,int r_minus=0) : l(l),r(r),dis(dis),l_plus(l_plus),l_minus(l_minus),r_plus(r_plus),r_minus(r_minus) {} _ operator + (const _ &rhs) const { _ ret; ret.l = l+max(rhs.l-r,0); ret.r = rhs.r+max(r-rhs.l,0); ret.l_plus = max({l_plus,l+r+rhs.l_minus,l-r+rhs.l_plus}); ret.l_minus = max(l_minus,rhs.l_minus+r-l); ret.r_plus = max({rhs.r_plus,r_plus-rhs.l+rhs.r,r_minus+rhs.l+rhs.r}); ret.r_minus = max(rhs.r_minus,r_minus+rhs.l-rhs.r); ret.dis = max({dis,rhs.dis,r_plus+rhs.l_minus,r_minus+rhs.l_plus}); return ret; } } tr[N<<2]; void build(int o, int l, int r) { if (l==r) tr[o]=_(s[l]==')',s[l]=='('); else build(ls),build(rs),tr[o]=tr[lc]+tr[rc]; } void update(int o, int l, int r, int x) { if (l==r) { if (s[l]=='(') s[l]=')',tr[o]=_(1,0); else s[l]='(',tr[o]=_(0,1); } else mid>=x?update(ls,x):update(rs,x),tr[o]=tr[lc]+tr[rc]; } int main() { scanf("%d%d%s", &n, &m, s+1); n <<= 1; build(1,1,n); printf("%d ", tr[1].dis); while (m--) { int x, y; scanf("%d%d", &x, &y); update(1,1,n,x); update(1,1,n,y); printf("%d ", tr[1].dis); } }