萌新代码只对subtask11,玄关求调
查看原帖
萌新代码只对subtask11,玄关求调
1344956
BestCNSoda楼主2024/12/18 22:46
#include<bits/stdc++.h>
#define N 500001
#define lx x<<1
#define rx x<<1|1
using namespace std;
int n,m,first,firstflag;
int tree[N<<3],tag[N<<3],a[N];
void pushup(int x)
{
    if(tree[lx]==tree[rx]) tree[x]=tree[lx];
    else
    tree[x]=0;
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        tree[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lx,l,mid);
    build(rx,mid+1,r);
    pushup(x);
}
void pushdown(int x)
{
    if(tag[x])
    {
        tree[lx]=tag[x];tree[rx]=tag[x];
        tag[x]=0;
    }
}
void update(int ll,int rr,int x,int l,int r,int k)
{
    if(ll<=l&&r<=rr)
    {
        tag[x]=k;
        tree[x]=k;
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(ll<=mid) update(ll,rr,lx,l,mid,k);
    if(rr>mid) update(ll,rr,rx,mid+1,r,k);
    pushup(x);
}
bool query(int ll,int rr,int x,int l,int r)
{
    if(ll<=l&&r<=rr)
    {
        if(firstflag==0)
        {
            firstflag=1;
            first=tree[x];
            return 1;
        }
        if(first!=tree[x]) return 0;
        else
        return 1;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    bool flag=1;
    if(ll<=mid) flag=(flag&&query(ll,rr,lx,l,mid));
    if(rr>mid) flag=(flag&&query(ll,rr,rx,mid+1,r));
    return flag;
}
int query1(int ll,int x,int l,int r)
{
    if(l==r)
    {
        return tree[x];
    }
    int mid=(l+r)>>1;
    if(ll<=mid) return query1(ll,lx,l,mid);
    else
    return query1(ll,rx,mid+1,r);
}
void print(int x,int l,int r)
{
    if(l==r)
    {
        cout<<tree[x]<<' ';
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    print(lx,l,mid);
    print(rx,mid+1,r);
    pushup(x);
}
int main()
{
    //freopen("4979.in","r",stdin);
    //freopen("4979.out","w",stdout);
    cin>>n;
    //getchar();
    for(int i=1;i<=n;i++)
    {
        char x;
        cin>>x;
        a[i]=(int)x-'A'+1;
        //cout<<a[i];
    }
    cin>>m;
    build(1,1,n);
    while(m--)
    {
        char x,op;
        int l,r;
        //getchar();
        cin>>x;
        scanf("%d%d",&l,&r);
        if(x=='A')
        {
            //getchar();
            cin>>op;
            //print(1,1,n);
            //cout<<endl;
            update(l,r,1,1,n,(int)op-'A'+1);
            //print(1,1,n);
        }
        if(x=='B')
        {
            firstflag=first=0;
            bool flag=query(l,r,1,1,n);
            if(flag==1)
            {
                if(l==1||r==n) {printf("Yes\n");continue;}
                int j=query1(l-1,1,1,n),k=query1(r+1,1,1,n);
                if(j!=k) {printf("Yes\n");continue;}
            }
            printf("No\n");
        }
    }
    return 0;
}

2024/12/18 22:46
加载中...