[DS记录]CF1340F Nastya and CBS

**题意** ： 你需要动态维护一个多种括号组成的，长度为 $n$ 的括号序列。需要支持两种操作： - 单点修改 - 查询 $[l,r]$ 区间是否是一个合法的括号序列。 $n,q\leq 10^5$ ，时限$\texttt{4s}$ ，空限$\texttt{250M}$。 ------------ 先考虑如何暴力回答单组询问。 用栈维护括号序列的匹配。若出现左括号，加入栈中。若出现右括号，查看栈顶是否为同类，若是，则弹栈，若不是（或栈为空），失配。 - ## 分块 对于每个块内，跑一次括号匹配。 此处允许栈为空的情况，此时要将右括号加入栈中。 若匹配时内部已经出现了失配，则对该块打上标记。 若没有失配，最终剩下的括号形如 $\texttt{)\})]\{(([}$ ，左边是一系列右括号，右边是一系列左括号。 回答询问时，将散块和整块的括号用栈再跑一次匹配。 先把散块按类似整块的方法整理。于是现在有若干段 “右右右左左左” 的括号序列等待合并。 这要求第 $i$ 组的左括号与第 $i+1$ 组的右括号完全匹配。使用 $\rm Hash$ 加速检验，复杂度可以做到 $O(q\sqrt{n})$。 - ## （兔队）线段树 对于每个线段树节点，维护内部匹配完之后剩下的括号，以及失配标记。 记左侧的右括号为 $ls$ ，右侧的左括号为 $rs$。为了方便维护，我们可以将 $ls$ 翻转。  记要合并的两个点为 $L,R$。考虑 $L.rs,R.ls$ ，不妨设 $R.ls$ 的长度较小，则将 $L.rs$ 抵消一部分，然后 $L.rs$ 剩余的一部分配上 $R.rs$ 为新的 $U.rs$ ，原来的 $L.ls$ 即为 $U.ls$。 于是，我们在合并时需要查询 $L.rs$ 前 $|R.ls|$ 个位置的 $\rm Hash$ 值。 记 $gR(U,k)$ 表示 $u.rs$ 长度为 $k$ 的前缀的 $\rm Hash$ 值。 若 $k=0$ 或者 $k=|U.rs|$ 可以直接返回结果。 否则，观察 $U.rs$ 是怎样得来的。 - $|L.rs|\leq |R.ls|$ 这时 $U.rs=R.rs$ ，直接递归右儿子。 - $|L.rs|>|R.ls|$ 这时 $U.rs=L.rs-R.ls+R.rs$ 。 若 $k\leq |L.rs|-|R.ls|$ ，直接递归左儿子。 若 $k> |L.rs|-|R.ls|$ ，则查询 $gR(R,k-(|L.rs|-|R.ls|))$ ，然后左侧加上 $L.rs-R.ls$。 综上， $gR$ 的复杂度为 $O(\log n)$ ，每次操作的复杂度也就是 $O(\log^2n)$ 的。 询问时需要将拆分出的节点用栈记录，特殊写一个 $\rm gL2$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; const int mod1=998244353,mod2=1000000007,Bas=114514; int pw1[MaxN],pw2[MaxN]; struct Str{int m,s1,s2;}; Str operator + (const Str &L,const Str &R) {return (Str){L.m+R.m,(L.s1+1ll*pw1[L.m]*R.s1)%mod1,(L.s2+1ll*pw2[L.m]*R.s2)%mod2};} Str operator - (const Str &S,const Str &T) {return (Str){S.m-T.m,(S.s1-1ll*T.s1*pw1[S.m-T.m])%mod1,(S.s2-1ll*T.s2*pw2[S.m-T.m])%mod2};} bool operator == (const Str &A,const Str &B) {return A.m==B.m&&(A.s1-B.s1)%mod1==0&&(A.s2-B.s2)%mod2==0;} struct Node{Str l,r;bool fl;}a[MaxN<<2]; void build(int k,Node &A){ if (k>0){A.l=(Str){0,0,0};A.r=(Str){1,k,k};} else {A.l=(Str){1,-k,-k};A.r=(Str){0,0,0};} } Str qryR(int l,int r,int u,int m) { if (m==0)return (Str){0,0,0}; if (m==a[u].r.m)return a[u].r; int mid=(l+r)>>1,L=u<<1,R=u<<1|1; if (a[L].r.m<=a[R].l.m)return qryR(mid+1,r,R,m); if (m<=a[L].r.m-a[R].l.m)return qryR(l,mid,L,m); return (a[L].r-a[R].l)+qryR(mid+1,r,R,m-(a[L].r.m-a[R].l.m)); } Str qryL(int l,int r,int u,int m) { if (m==0)return (Str){0,0,0}; if (m==a[u].l.m)return a[u].l; int mid=(l+r)>>1,L=u<<1,R=u<<1|1; if (a[R].l.m<=a[L].r.m)return qryL(l,mid,L,m); if (m<=a[R].l.m-a[L].r.m)return qryL(mid+1,r,R,m); return (a[R].l-a[L].r)+qryL(l,mid,L,m-(a[R].l.m-a[L].r.m)); } void up(int tl,int tr,int u) { int l=u<<1,r=u<<1|1,mid=(tl+tr)>>1; if (a[l].fl||a[r].fl){a[u].fl=1;return ;} if (a[l].r.m>=a[r].l.m){ if (qryR(tl,mid,l,a[l].r.m-a[r].l.m)==a[l].r-a[r].l){ a[u].fl=0; a[u].l=a[l].l; a[u].r=(a[l].r-a[r].l)+a[r].r; }else a[u].fl=1; }else { if (qryL(mid+1,tr,r,a[r].l.m-a[l].r.m)==a[r].l-a[l].r){ a[u].fl=0; a[u].r=a[r].r; a[u].l=(a[r].l-a[l].r)+a[l].l; }else a[u].fl=1; } } int s[MaxN]; void build(int l,int r,int u) { if (l==r){build(s[l],a[u]);return ;} int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(l,r,u); } int to,wfc; void chg(int l,int r,int u) { if (l==r){build(wfc,a[u]);return ;} int mid=(l+r)>>1; if (to<=mid)chg(l,mid,u<<1); else chg(mid+1,r,u<<1|1); up(l,r,u); } struct Data{int l,r,u;}st[55]; Str sr[55]; int wfl,wfr,tn;bool fl; Str qryR2(int p,int m) { if (m==0)return (Str){0,0,0}; if (m==sr[p].m)return sr[p]; Data &U=st[p]; if (m<=sr[p-1].m-a[U.u].l.m)return qryR2(p-1,m); return (sr[p-1]-a[U.u].l)+qryR(U.l,U.r,U.u,m-(sr[p-1].m-a[U.u].l.m)); } void qry(int l,int r,int u) { if (fl)return ; if (wfl<=l&&r<=wfr){ if (a[u].fl||sr[tn].m<a[u].l.m){fl=1;return ;} if (qryR2(tn,sr[tn].m-a[u].l.m)==sr[tn]-a[u].l){ st[++tn]=(Data){l,r,u}; sr[tn]=(sr[tn-1]-a[u].l)+a[u].r; }else fl=1; return ; }int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int n,m; int main() { scanf("%d%*d",&n); pw1[0]=pw2[0]=1; for (int i=1;i<=n;i++){ pw1[i]=1ll*pw1[i-1]*Bas%mod1; pw2[i]=1ll*pw2[i-1]*Bas%mod2; } for (int i=1;i<=n;i++)scanf("%d",&s[i]); build(1,n,1); scanf("%d",&m); for (int i=1,op;i<=m;i++){ scanf("%d",&op); if (op==1){ scanf("%d%d",&to,&wfc); chg(1,n,1); }else { scanf("%d%d",&wfl,&wfr); fl=tn=0;qry(1,n,1); puts(fl||sr[tn].m ? "No" : "Yes"); } }return 0; } ```