Logo zrl123456 的博客

博客

[ABC341E] Alternating String 讲解

...
zrl123456
2025-12-01 12:51:25
我咋啥也不会/ll

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-11 22:35:25

题目
考察：线段树，树状数组，set，差分。

方法一：

这道题与 P3870 有点相似，只不过它是区间求和，而这道题是判断是不是好字符串。
我们不难发现，好的字符串有以下特征：

  1. 好的字符串取反后必为好的字符串（不好的字符串取反后必为不好的字符串）。
  2. 好的字符串的子串必为好的字符串（不好的字符串的母串必为不好的字符串）。

然后我们来看个图：

所以说我们要存三个值：首端点值，尾端点值和判断变量，我们分别用 $begin$，$end$，$vis$ 表示（当然懒标记也是需要的，我们用 $lan$ 表示）。
我们得到状态转移方程：
$$vis_x=[vis_u\lor vis_v\lor (end_u\ne begin_v)]$$ $$begin_x=begin_u$$ $$end_x=end_v$$ 边界条件为（$l=r$）：
$$vis_x=1$$ $$begin_x=end_x=a_l$$ 修改时：
$$lan_x=1-lan_x$$ pushdown 函数：
$$begin_u=1-begin_u$$ $$end_u=1-end_u$$ $$begin_v=1-begin_v$$ $$end_v=1-end_v$$ $$lan_u=lan_v=1$$ $$lan_x=0$$ 易得代码（时间：$427ms$，空间：$47.53MB$，代码长度：$2.64KB$，是三种做法之中最劣的一种做法）：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
const int N=5e5+5;
struct trees{
	int l,r,begin,end;
	bool vis,lan;
}t[N<<2];
string s;
int n,q,a[N],op,l,r;
inl void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].vis=1;
		t[x].begin=a[l];
		t[x].end=a[r];
\/\/		cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x].vis=(t[x<<1].vis&&t[x<<1|1].vis&&t[x<<1].end!=t[x<<1|1].begin);
	t[x].begin=t[x<<1].begin;
	t[x].end=t[x<<1|1].end;
\/\/	cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
}
inl void pushdown(int x){
	if(!t[x].lan) return;
	t[x<<1].begin^=1;
	t[x<<1].end^=1;
	t[x<<1|1].begin^=1;
	t[x<<1|1].end^=1;
	t[x<<1].lan^=1;
	t[x<<1|1].lan^=1;
\/\/	cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
\/\/	cout<<(x<<1)<<' '<<t[x<<1].l<<' '<<t[x<<1].r<<' '<<t[x<<1].begin<<' '<<t[x<<1].end<<' '<<t[x<<1].vis<<endl;
\/\/	cout<<(x<<1|1)<<' '<<t[x<<1|1].l<<' '<<t[x<<1|1].r<<' '<<t[x<<1|1].begin<<' '<<t[x<<1|1].end<<' '<<t[x<<1|1].vis<<endl;
	t[x].lan=0;
}
inl void add(int x,int l,int r){
	if(l<=t[x].l&&t[x].r<=r){
		t[x].lan^=1;
		t[x].begin^=1;
		t[x].end^=1;
\/\/		cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
		return;
	}
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid) add(x<<1,l,r);
	if(mid<r) add(x<<1|1,l,r);
	t[x].vis=(t[x<<1].vis&&t[x<<1|1].vis&&t[x<<1].end!=t[x<<1|1].begin);
	t[x].begin=t[x<<1].begin;
	t[x].end=t[x<<1|1].end;
\/\/	cout<<x<<' '<<t[x].l<<' '<<t[x].r<<' '<<t[x].begin<<' '<<t[x].end<<' '<<t[x].vis<<endl;
}
inl bool getans(int x,int l,int r){
	if(l<=t[x].l&&t[x].r<=r) return t[x].vis;
	pushdown(x);
	int mid=(t[x].l+t[x].r)>>1;
	bool vis=1;
	if(l<=mid) vis&=getans(x<<1,l,r);
	if(r>mid) vis&=getans(x<<1|1,l,r);
	if(l<=mid&&r>mid) vis&=(t[x<<1].end!=t[x<<1|1].begin);
	return vis;
}
signed main(){
	n=read();
	q=read();
	cin>>s;
	s=' '+s;
	for(int i=1;i<=n;++i) a[i]=s[i]^48;
	build(1,1,n);
	for(int i=1;i<=q;++i){
		op=read();
		l=read();
		r=read();
		if(op==1) add(1,l,r);
		else if(getans(1,l,r)) puts("Yes");
		else puts("No");
	}
	return 0;
}

做法 2：

看到相邻两个数不同，我们便想到差分，样例中的数列差分后就是下面这个样子：
$$c=\{1,1,1,1,0\}$$ 恍然大悟，不就是转化成了单点修改（修改左右两个端点），区间求和（若区间内的和正好等于长度，也就是每个元素都为 $1$ 时，就为好的字符串）嘛。
代码没什么好讲的，但需要注意两个点：

  1. 第 $1$ 个点上的差分数组始终为 $1$。
  2. 第 $l$ 个点上存的是第 $l-1$ 个点与它的差分，不能算入查询区间里。

代码（时间：$223ms$，空间：$31.55MB$，代码长度：$1.48KB$，就时间来看，它是三种做法的最优解）：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
const int N=5e5+5;
struct trees{
	int l,r,sum;
}t[N<<2];
string s;
int n,q,a[N],op,l,r;
inl void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inl void add(int x,int vis){
	if(t[x].l==vis&&vis==t[x].r){
		t[x].sum^=1;
		return;
	}
	int mid=(t[x].l+t[x].r)>>1;
	if(vis<=mid) add(x<<1,vis);
	else add(x<<1|1,vis);
	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inl int getans(int x,int l,int r){
	if(l<=t[x].l&&t[x].r<=r) return t[x].sum;
	int mid=(t[x].l+t[x].r)>>1,sum=0;
	if(l<=mid) sum+=getans(x<<1,l,r);
	if(r>mid) sum+=getans(x<<1|1,l,r);
	return sum;
}
signed main(){
	n=read();
	q=read();
	cin>>s;
	s=' '+s;
	a[1]=1;
	for(int i=2;i<=n;++i) a[i]=s[i-1]^s[i];
	build(1,1,n);
	for(int i=1;i<=q;++i){
		op=read();
		l=read();
		r=read();
		if(op==1){
			if(l!=1) add(1,l);
			if(r!=n) add(1,r+1);
		}else if(getans(1,l+1,r)==r-l) puts("Yes");
		else puts("No");
	}
	return 0;
}

做法 3：

做法 $3$ 很巧妙，同样做了差分，但把相同的放在了 set 里，修改的时候左右端点 set 里有就删除，没有就插入，最后直接查询。
要注意的还是上面那两个，不多说直接放代码（时间：$705ms$，空间：$26.59MB$，代码长度：$982B$，虽说跑的最慢，但代码空间大大减少）：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
#define T set<int>::iterator
string s;
int n,q,op,l,r;
set<int>st;
signed main(){
	n=read();
	q=read();
	cin>>s;
	s=' '+s;
	for(int i=1;i<=n;++i)
		if(s[i]==s[i-1]) st.insert(i);
	for(int i=1;i<=q;++i){
		op=read();
		l=read();
		r=read();
		if(op==1){
			if(st.find(l)==st.end()&&l!=1) st.insert(l);
			else st.erase(l);
			if(st.find(r+1)==st.end()) st.insert(r+1);
			else st.erase(r+1);
		}else{
			T it=st.upper_bound(l);
			if(it==st.end()||*it>r) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

（真的想吐槽一下专栏区）

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

服务器时间: 2026-03-17 23:04:42 | 开源项目