ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF1477B Nezzar and Binary String 题解

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

据说很简单?所以就来看看了。

这题最关键的地方在于严格小于一半。因为全是01,只可能有一种数量严格小于一半,所以每次操作的东西其实不用决策就已经确定了。用线段树模拟一下即可,最后一次需要单独处理。

等等,然后你发现我读错题了,是先检查再操作,而不是先操作再检查啊?诶再等等,这么一说出来,发现时间倒流一下就可以了?

这个题启示我们,要注意一些不太寻常的东西,比如别的题都是$\leq$,为什么就你是$<$?

然后就是读错题有时候也是好事(然而大部分时候是坏事

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

inline void add_tag(int u,int v)
{
    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)
        add_tag(lq(u),t[u].tag),
        add_tag(rq(u),t[u].tag),
        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)
    {
        add_tag(u,val);
        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;
}