专栏文章

题解：P13274 [NOI2025] 三目运算符

__droplet_
P13274题解参与者 6已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miotaruv
此快照首次捕获于
2025/12/03 00:48
3 个月前
此快照最后确认于
2025/12/03 00:48
3 个月前
查看原文
  • update in 2025.11.26 感谢 tallnut提供的定义问题，已经修改。

前置知识

线段树。

思路

考虑对于字符串每一位 ii，影响到这一位的只会有第 ii 位，第 i−1i-1 位和 i−2i-2 位，手搓 33 位字符串可以发现：
  • 101 的情况可以更新 11 次。
  • 110 的情况可以更新到字符串结尾，次数为字符串长度减该字串内最左侧字符位置再减 11。
考虑用线段树维护这个操作，记录内容如下：
  • b1b1 表示是否有 1...10（00 的数量为任意非负整数）的情况，记录这个字符串的第一个 1 的位置。
  • b0b0 表示是否有 0...01（11 的数量为任意非负整数）的情况，记录这个字符串的第一个 0 的位置，因为有区间异或操作，所以需要维护零的情况。
  • l0l0 表示某线段左侧 00 的数量。
  • l1l1 表示某线段左侧 11 的数量。
  • r0r0 表示某线段右侧 00 的数量。
  • r1r1 表示某线段右侧 11 的数量。
  • vl1vl1 表示是否有 101 的情况。
  • vl0vl0 表示是否有 010 的情况。

具体操作

pushup

更新区间维护的所有信息。
对于每个点，设其为 xx，其左子树为 lsls，其右子树为 rsrs。
  • 更新 l0l0 时，若左子树 l0l0 等于左子树区间长度，l0x=lsize+l0rsl0_x=lsize+l0_{rs}，否则 l0x=l0rsl0_x=l0_{rs}。
  • 更新 l1l1，r0r0，r1r1 同上操作。
  • 更新 vl1vl1 时，若出现左子树末尾为 ...10，右子树开头为 1... 的情况，vl1x=1vl1_x=1；若出现左子树末尾为 ...1，右子树开头为 01... 的情况，vl1x=1vl1_x=1；否则为左右子树 vl1vl1 的最大值。
  • 更新 vl0vl0 同上操作。
  • 更新 b1b1 时，若出现左子树末尾为，右子树开头为连续 1 的情况，且左子树的 b1b1 在这个范围内，b1x=min⁡{mid+l1rs−1,b1rs}b1_x=\min\{mid+l1_{rs}-1,b1_{rs}\}，否则 b1xb1_x 为左子树的 b1b1，右子树的 b1b1 和中间满足条件位置的最小值。
  • 更新 b0b0 同上操作。

pushdown

交换对应的每一组两个数，更新懒标记。

特殊初始值

  • b1b1 初始值为极大值。
  • b0b0 初始值为极大值。
  • vl1vl1 初始值为 00。
  • vl0vl0 初始值为 00。

代码

CPP
#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;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...