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

中文题意:

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

每次询问有区间 \([\ l,r\ ]\)
,如果 \([\ l,r\ ]\)
同时包含 \(0\)
和 \(1\)
，则询问终止，否则你可以将区间 \([\ l,r\ ]\)
内严格小于 \(len_{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\)
)的数量 \(num_{k\oplus 1}\)
\(<\)
\(len_{lr}\)
时,

\(s_{n-1}\)
可转化 \(f\)
。

那么，我们可以从 \(f\)
开始向前遍历询问。对于 \([l_{n},r_{n}]\)
, 将 \([l_{n},r_{n}]\)
内数量较少的数字改为另一个数字。

显然
，当 \([l_{n},r_{n}]\)
内 \(num_{1} = num_{0}\)
时，询问会终止，因为改变量必须严格小于区间长度的一半。

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

做法:

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

首先对于 \(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;
}

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

Code:

#include
#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'9'){if(a=='-')w=-1;a=getchar();}
    while(a='0'){x=(x<<3)+(x<>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;
    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>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>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=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;
}