题解：P13274 [NOI2025] 三目运算符
- update in 2025.11.26 感谢 @tallnut 提供的定义问题，已经修改。
\Large\textup{\textmd{Solution}}
线段树。
考虑对于字符串每一位
101的情况可以更新1 次。110的情况可以更新到字符串结尾，次数为字符串长度减该字串内最左侧字符位置再减1 。
考虑用线段树维护这个操作，记录内容如下：
\Large\textup{\textmd{Instruction}}
\textup{\textbf{Pushup}}
更新区间维护的所有信息。
对于每个点，设其为
- 更新
l0 时，若左子树l0 等于左子树区间长度，l0_x=lsize+l0_{rs} ，否则l0_x=l0_{rs} 。 - 更新
l1 ，r0 ，r1 同上操作。 - 更新
vl1 时，若出现左子树末尾为...10，右子树开头为1...的情况，vl1_x=1 ；若出现左子树末尾为...1，右子树开头为01...的情况，vl1_x=1 ；否则为左右子树vl1 的最大值。 - 更新
vl0 同上操作。 - 更新
b1 时，若出现左子树末尾为，右子树开头为连续1的情况，且左子树的b1 在这个范围内，b1_x=\min\{mid+l1_{rs}-1,b1_{rs}\} ，否则b1_x 为左子树的b1 ，右子树的b1 和中间满足条件位置的最小值。 - 更新
b0 同上操作。
\textup{\textbf{Pushdown}}
交换对应的每一组两个数，更新懒标记。
\textup{\textbf{Inital Value}}
\Large\textup{\textmd{Code}}
#include<bits/stdc++.h>
#define int long long
#define tag(x) st[x].tag
#define vl0(x) st[x].vl0
#define vl1(x) st[x].vl1
#define ls(x) st[x].ls
#define rs(x) st[x].rs
#define b0(x) st[x].b0
#define b1(x) st[x].b1
#define l0(x) st[x].l0
#define l1(x) st[x].l1
#define r0(x) st[x].r0
#define r1(x) st[x].r1
#define lsz mid-l+1
#define rsz r-mid
#define sz r-l+1
using namespace std;
const int N=800010;
int n,m,a[N];
struct treenode{
int ls,rs,b0,b1,l0,l1,r0,r1,vl0,vl1,tag;
}st[N];
struct segtree{
int rt,tc;
void pushup(int x,int l,int r){ // 同上描述
int mid=(l+r)>>1;
vl0(x)=max(vl0(ls(x)),vl0(rs(x)));
vl1(x)=max(vl1(ls(x)),vl1(rs(x)));
if(r0(ls(x))&&l0(rs(x))){
b0(x)=min(mid+l0(rs(x))-1,b0(rs(x)));
if(b0(ls(x))<mid-r0(ls(x))+1) b0(x)=min(b0(x),b0(ls(x)));
}else b0(x)=min(b0(ls(x)),b0(rs(x)));
if(r1(ls(x))&&l1(rs(x))){
b1(x)=min(mid+l1(rs(x))-1,b1(rs(x)));
if(b1(ls(x))<mid-r1(ls(x))+1) b1(x)=min(b1(x),b1(ls(x)));
}else b1(x)=min(b1(ls(x)),b1(rs(x)));
l0(x)=(l0(ls(x))!=lsz?l0(ls(x)):lsz+l0(rs(x)));
l1(x)=(l1(ls(x))!=lsz?l1(ls(x)):lsz+l1(rs(x)));
r0(x)=(r0(rs(x))!=rsz?r0(rs(x)):rsz+r0(ls(x)));
r1(x)=(r1(rs(x))!=rsz?r1(rs(x)):rsz+r1(ls(x)));
if((r0(ls(x))&&l1(rs(x))==1&&rsz>1)||(r1(ls(x))==1&&l0(rs(x))&&lsz>1)) vl0(x)=max(vl0(x),1ll);
if((r0(ls(x))==1&&l1(rs(x))&&lsz>1)||(r1(ls(x))&&l0(rs(x))==1&&rsz>1)) vl1(x)=max(vl1(x),1ll);
}
void pushdown(int x){ // 同上描述
if(!tag(x)) return;
tag(ls(x))^=tag(x);
tag(rs(x))^=tag(x);
swap(vl0(ls(x)),vl1(ls(x))),swap(vl0(rs(x)),vl1(rs(x)));
swap(b0(ls(x)),b1(ls(x))), swap(b0(rs(x)),b1(rs(x)));
swap(l0(ls(x)),l1(ls(x))), swap(l0(rs(x)),l1(rs(x)));
swap(r0(ls(x)),r1(ls(x))), swap(r0(rs(x)),r1(rs(x)));
tag(x)=0;
}
void build(int &x,int l,int r){
x=++tc;
tag(x)=0;
b0(x)=b1(x)=2*n;
vl0(x)=vl1(x)=0;
l1(x)=r1(x)=l0(x)=r0(x)=0;
if(l==r){
if(a[l]){ // 根据输入更新
l1(x)=r1(x)=1;
l0(x)=r0(x)=0;
}else{
l1(x)=r1(x)=0;
l0(x)=r0(x)=1;
}
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x,l,r);
}
void update(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
tag(x)^=1;
swap(vl0(x),vl1(x));
swap(b0(x),b1(x));
swap(l0(x),l1(x));
swap(r0(x),r1(x));
return;
}
pushdown(x);
int mid=(l+r)>>1;
if(ql<=mid) update(ls(x),l,mid,ql,qr);
if(mid<qr) update(rs(x),mid+1,r,ql,qr);
pushup(x,l,r);
}
int query(){
int ans=vl1(rt);
if(b1(rt)!=2*n) ans=max(ans,n-b1(rt)-1); // 输出答案为 vl1 和 b1 位置更新到末尾的最大值
return ans;
}
void print(int x,int l,int r){ // 调试用
cout<<x<<"|"<<l<<"|"<<r<<"|\tvl0 "<<vl0(x)<<"\tvl1 "<<vl1(x)<<"\tl0 "<<l0(x)<<"\tl1 "<<l1(x)<<"\tr0 "<<r0(x)<<"\tr1 "<<r1(x)<<"\tb0 "<<b0(x)<<"\tb1 "<<b1(x)<<"\n";
pushdown(x);
if(l==r) return;
int mid=(l+r)>>1;
print(ls(x),l,mid);
print(rs(x),mid+1,r);
}
}t;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T>>T;
while(T--){
t.tc=0;
cin>>n>>m;
char c;
for(int i=1;i<=n;i++){
cin>>c;
a[i]=c-'0';
}
t.build(t.rt,1,n);
// t.print(t.rt,1,n);
// cout<<t.query()<<"\n";
int l,r,ans=0;
ans=t.query();
for(int i=2;i<=m+1;i++){
cin>>l>>r;
t.update(t.rt,1,n,l,r);
// t.print(t.rt,1,n);
// cout<<t.query()<<"\n";
ans^=i*t.query();
}
cout<<ans<<"\n";
}
return 0;
}