Codeforces #698 (Div. 2) E. Nezzar and Binary String 题解

中文题意:

$T$ 组数据

给你两个长度为 $n$ 的01串 $s,f,$有 $q$ 次询问。

每次询问有区间 $[l,r]$ ,如果 $[l,r]$ 同时包含$0$和$1$，则询问终止，否则你可以改变区间$[l,r]$ 内严格小于 $le{n}_{lr}$ 的数字。

问是否可以使得询问不终止，且经过 $q$ 次询问后可以将$s$改为$f$。

前置知识:

线段树

没了

思路:

发现没法正序推过去(反正我不会)，考虑根据询问逆推。

那么对于 $f$ ,和 $q_1,q_2$···$q_n$ ,用 $l_i,r_i$ 来表示 $q_i$ , $s_i$表示经过前 $i$ 次询问后的字符串 $s$ 。

对于第 $n$ 次询问，当且仅当 $s_{n-1}$中的 $[l_n,r_n]$ 全为 $k$ ( $k$ $\in$ $(0,1)$ ) ,$f$ 在 $[l_n,r_n]$ 内($k\oplus 1$)的数量$nu{m}_{k\oplus 1}$ $<$ $le{n}_{lr}$ 时,

$s_{n-1}$ 可转化 $f$ 。

因此，我们可以对于 $f$ 从 $n$ 开始向前遍历询问。对于 $[l_i,r_i]$ , 将 $[l_i,r_i]$ 内数量较少的数字改为另一个数字。

显然，当 $[l_i,r_i]$ 内 $nu{m}_1=nu{m}_0$ 时，询问会终止，因为改变量必须严格小于区间长度的一半。

遍历到最后判断 $s$ 和经过转化的 $f$ 是否相同就行了。

做法:

对于区间，查询和改变问题，我们可以用线段树在 $logn$ 的复杂度下解决。

首先对于 $f$ 建立线段树，维护区间内 $1$ 的数量。

对于区间修改，建立 $lazy$ 标记，$-1$ 表示不变，$0$ 表示 $lazy$ 下的区间全为$0$，$1$ 表示 $lazy$ 下的区间全为$1$。

$pusdown$ 操作:

inline void pushdown(int p,int l,int r)
{
	if(laz[p]==-1)//未被标记跳过
		return ;
	int mid=(l+r)>>1;
	if(laz[p])//标记为1
	{
		tr[p<<1]=(mid-l+1);
		tr[p<<1|1]=(r-mid);
		laz[p<<1]=laz[p<<1|1]=1;
		laz[p]=-1;
		return ;
	}
	tr[p<<1]=tr[p<<1|1]=0;//标记为0
	laz[p<<1]=laz[p<<1|1]=0;
	laz[p]=-1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剩下的就是线段树的基本操作了。

Code:

#include<bits/stdc++.h>
#define N 240000
using namespace std;
 
int t,n,q;
char s[N],f[N];
int ql[N],qr[N],tr[N<<2],laz[N<<2];
 
inline int read()
{
	char a=0;int w=1,x=0;
	while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
	while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
	return x*w;
}
 
inline void pushdown(int p,int l,int r)
{
	if(laz[p]==-1)//未被标记跳过
		return ;
	int mid=(l+r)>>1;
	if(laz[p])//标记为1
	{
		tr[p<<1]=(mid-l+1);
		tr[p<<1|1]=(r-mid);
		laz[p<<1]=laz[p<<1|1]=1;
		laz[p]=-1;
		return ;
	}
	tr[p<<1]=tr[p<<1|1]=0;//标记为0
	laz[p<<1]=laz[p<<1|1]=0;
	laz[p]=-1;
}
 
void build(int p,int l,int r)//建树
{
	laz[p]=-1;
	if(l==r)
	{
		tr[p]=(f[l]^48);
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
 
int que(int p,int l,int r,int L,int R)//查询1的数量
{
	if(L<=l&&r<=R)
		return tr[p];
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	int ans=0;
	if(mid>=L)
		ans+=que(p<<1,l,mid,L,R);
	if(mid<R)
		ans+=que(p<<1|1,mid+1,r,L,R);
	return ans;
}
 
void modify(int p,int l,int r,int L,int R,int opt)//区间修改
{
	if(L<=l&&r<=R)
	{
		tr[p]=opt*(r-l+1);
		laz[p]=opt;
		return ;
	}
	pushdown(p,l,r);
	int mid=(l+r)>>1;
	if(mid>=L)
		modify(p<<1,l,mid,L,R,opt);
	if(mid<R)
		modify(p<<1|1,mid+1,r,L,R,opt);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
 
int main()
{
	t=read();
	while(t--)
	{
		n=read();
		q=read();
		int flag=1;
		scanf("%s%s",(s+1),(f+1));
		for(register int i=1;i<=q;i++)
		{
			ql[i]=read();
			qr[i]=read();
		}
		build(1,1,n);
		for(register int i=q;i>=1;i--)
		{
			int len=qr[i]-ql[i]+1;//区间长度
			int num=que(1,1,n,ql[i],qr[i]);//查询区间内1的数量
			if( num==len-num )//区间内0的数量为 len-num , 0和1数量相同时不可能成立
			{
				flag=0;
				break;
			}
			modify(1,1,n,ql[i],qr[i],num>(len-num) );//区间修改
		}
		if(!flag)
		{
			printf("NO\n");
			continue;
		}
		for(register int i=1;i<=n;i++)
		{
			int num=que(1,1,n,i,i);//取出经过q次询问后f的第i位
			if(num!=(s[i]^48))//判断f和s是否相等，不相等退出
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			printf("NO\n");
			continue;
		}
		printf("YES\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128