20260612模拟赛
红蓝树
题面：
有一个栈，栈有两种状态，无色和蓝色，有三种操作，
1.将一棵红树苗加入栈顶，若栈为蓝色，则将此棵红树苗变为蓝树苗，并将栈变为无色。
2.将一棵蓝树苗加入栈顶，若栈为蓝色，则将栈变为无色。
3.将栈顶的树苗弹出，若树苗为蓝色，则将栈变为蓝色。如果在弹出前栈已经为空，则什么都不会发生。
小 T 有一个长为 \(n\) 的操作序列 \(a\)，其中 \(a_i\in\{1,2,3\}\) 代表了第 \(i\) 个操作是上述的第几种操作。
小 T 有 \(m\) 次修改或询问，形如：
- 1 l r 表示对所有 \(i\in[l,r]\)，若 \(a_i=1\) 则改为 2，否则若 \(a_i=2\) 则改为 1。
- 2 l r 表示从空栈开始，依次进行操作 \(a_l,a_{l+1},\ldots,a_r\)，询问这个过程中一共有多少蓝色的树苗。
\(n\leq 600000\)
题解：
首先括号匹配找到每个树苗被弹出的时刻。那么一棵树苗 \(u\) 只可能对它弹出之后的第一个加入的树苗 \(v\) 产生影响，连有向边 \((u,v)\)。特别地，若之后没有加入树苗则向 \(n+1\) 连边。
得到一棵树，每棵蓝树苗都会让它的所有祖先变蓝。给定询问区间 \([l,r]\) 之后，相当于是把 \([l,r]\) 中加入的树苗拿出来，在它们对应的点在树上的导出子图上询问。
加入树苗的顺序，也正好对应了树上 dfs 序的倒序。假设最后弹出的树苗形如 \(.......(.........)\)，其中加入/弹出的时刻为左/右括号，可以在树上先 dfs 括号里，再 dfs 这个树苗，以及它左边的子树。总可以在末尾添加 3 操作使得所有树苗均被弹出。
题意变为在一棵树上，有红点和蓝点，支持 dfs 序区间翻转颜色，以及给出 dfs 序区间 \([l,r]\) ，查询这些点构成的森林对应的答案。如果询问时的点构成了一棵连通子树，那么答案是蓝点与根构成的虚树的大小，相邻两蓝点距离和的一半。
但 dfs 序区间可以不连通，我们需要想办法把它变成连通的。记 dfs 序为 \(l-1\) 的点为 \(u\)，如果再加入 \(u\) 到根的路径上的所有点，那么这些点即可构成连通子树。考虑消除加入的链的影响，链上有一个前缀是蓝色的，第一次变蓝的位置是点 \(u\) 与区间 \([l,r]\) 中 dfs 序最小的蓝点的 LCA。
线段树维护区间 \([l,r]\) 相邻蓝点距离，dfs 序最小最大蓝点即可。
代码
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;inline int read(){int s=0,k=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') k=-1;c=getchar();}while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+(c^48);c=getchar();}return s*k;
}const int N=6e5+5;
int n,a[N],pre[N],suf[N],dep[N],st[22][N<<1],lgn[N<<1],tim,m,ids[N],id[N],dfn[N],Q;
vector<int>e[N];
struct node{int s,l,r;
};
struct Tree{node v,s;int tag;
}t[N<<2];void dfs(int x){st[0][++tim]=x;ids[x]=tim;for(int v:e[x]){dep[v]=dep[x]+1;dfs(v);st[0][++tim]=x;}
}int cmin(int x,int y){return dep[x]<dep[y]?x:y;
}int LCA(int x,int y){int l=ids[x],r=ids[y];if(l>r) swap(l,r);int mn=lgn[r-l+1];return cmin(st[mn][l],st[mn][r-(1<<mn)+1]);
}int Dis(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];
}node pushup(node L,node R){if(!L.l&&!L.r) return R;if(!R.l&&!R.r) return L;node S;S.l=L.l;S.r=R.r;S.s=L.s+R.s+Dis(L.r,R.l);return S;
}void pushup(int s){t[s].v=pushup(t[s<<1].v,t[s<<1|1].v);t[s].s=pushup(t[s<<1].s,t[s<<1|1].s);
}void upd(int s){t[s].tag^=1;swap(t[s].s,t[s].v);
}void pushdown(int s){if(t[s].tag){upd(s<<1);upd(s<<1|1);t[s].tag=0;}
}void build(int s,int l,int r){if(l==r){t[s].v={0,0,0};t[s].s={0,id[l],id[l]};if(a[id[l]]==2) swap(t[s].s,t[s].v);return ;}int mid=l+r>>1;build(s<<1,l,mid);build(s<<1|1,mid+1,r);pushup(s);
}void update(int s,int l,int r,int L,int R){if(L<=l&&r<=R){upd(s);return ;}pushdown(s);int mid=l+r>>1;if(L<=mid) update(s<<1,l,mid,L,R);if(R>mid) update(s<<1|1,mid+1,r,L,R);pushup(s);
}node query(int s,int l,int r,int L,int R){if(L<=l&&r<=R) return t[s].v;pushdown(s);int mid=l+r>>1;if(R<=mid) return query(s<<1,l,mid,L,R);if(L>mid) return query(s<<1|1,mid+1,r,L,R);return pushup(query(s<<1,l,mid,L,R),query(s<<1|1,mid+1,r,L,R));
}int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);n=read();Q=read();for(int i=1;i<=n;i++) a[i]=read();{vector<int>vec;stack<int>st;for(int i=1;i<=n;i++){if(a[i]==3){if(st.size()){vec.push_back(st.top());st.pop();}}else{e[i]=vec;vec.clear();st.push(i);}}e[n+1]=vec;while(st.size()){e[n+1].push_back(st.top());st.pop();}}dfn[n+1]=++m;id[m]=n+1;for(int i=n;i>=1;i--)if(a[i]!=3){dfn[i]=++m;id[m]=i;}for(int i=1,lst=0;i<=n;i++){if(a[i]!=3) lst=i;pre[i]=lst;}for(int i=n,lst=n+1;i>=1;i--){if(a[i]!=3) lst=i;suf[i]=lst;}dfs(n+1);for(int i=2;i<=tim;i++) lgn[i]=lgn[i>>1]+1;for(int j=1;j<=lgn[tim];j++)for(int i=1;i+(1<<j)-1<=tim;i++)st[j][i]=cmin(st[j-1][i],st[j-1][i+(1<<j-1)]);build(1,1,m);while(Q--){int op=read(),l=read(),r=read();l=dfn[suf[l]];r=dfn[pre[r]];swap(l,r);if(l>r){if(op==2) printf("0\n");continue;}if(op==1) update(1,1,m,l,r);else{int u=id[l-1];node v=query(1,1,m,l,r);if(!v.l&&!v.r) printf("0\n");else printf("%d\n",(v.s+dep[v.l]+dep[v.r])/2-dep[LCA(u,v.l)]);}}return 0;
}