# ShanLunjiaJian的blog

### CF1477B Nezzar and Binary String 题解

posted on 2021-01-29 01:41:31 | under 题解 |

#include<stdio.h>

int n,q,s[200002],f[200002],l[200002],r[200002];
char ss[200002],ff[200002];

struct Node
{
int l,r,sum,tag;
}t[800002];

#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)

inline void push_up(int u)
{
t[u].sum=t[lq(u)].sum+t[rq(u)].sum;
}

{
t[u].tag=v;
t[u].sum=(t[u].r-t[u].l+1)*v;
}

inline void push_down(int u)
{
if(t[u].tag!=-1)
t[u].tag=-1;
}

void build(int l,int r,int u)
{
t[u].l=l,t[u].r=r;
t[u].tag=-1;
if(l==r)
{
t[u].sum=f[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,lq(u));
build(mid+1,r,rq(u));
push_up(u);
}

void change(int l,int r,int u,int val)
{
if(l<=t[u].l&&t[u].r<=r)
{
return;
}
int mid=(t[u].l+t[u].r)>>1;
push_down(u);
if(l<=mid) change(l,r,lq(u),val);
if(mid+1<=r) change(l,r,rq(u),val);
push_up(u);
}

int query(int l,int r,int u)
{
if(l<=t[u].l&&t[u].r<=r)
return t[u].sum;
int mid=(t[u].l+t[u].r)>>1;
push_down(u);
return (l<=mid?query(l,r,lq(u)):0)+(mid+1<=r?query(l,r,rq(u)):0);
}

bool dfs(int u)
{
if(t[u].l==t[u].r)
if(t[u].sum!=s[t[u].l]) return 1;
else return 0;
else return push_down(u),dfs(lq(u))||dfs(rq(u));
}

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%s%s",&n,&q,ss+1,ff+1);
for(int i=1;i<=n;i++)
s[i]=ss[i]-'0',f[i]=ff[i]-'0';
build(1,n,1);
for(int i=1;i<=q;i++)
scanf("%d%d",&l[i],&r[i]);
bool flag=0;
for(int i=q,temp,len;!flag&&i>=1;i--)
{
temp=query(l[i],r[i],1);
len=r[i]-l[i]+1;
if(2*temp<len)
change(l[i],r[i],1,0);
else if(2*(len-temp)<len)
change(l[i],r[i],1,1);
else
{
flag=1;
printf("NO\n");
break;
}
}
if(!flag&&dfs(1)) flag=1,printf("NO\n");
if(!flag) printf("YES\n");
}
return 0;
}