洛谷P4979 矿洞:坍塌

@Pelom  November 3, 2019

题意

给出一个字符串,$2$种操作

  • 区间覆盖
  • 询问是否区间内相同,两端不同

数据范围:$n,k \le 500000$

题解

容易想到用线段树
维护每个区间的颜色,相同则为原值,不同则为此外的值(如'0')
注意询问的判断条件

代码:

#include<iostream>
#include<cstdio>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int N=500000+10;
int n,k,l,r;
char op[1],p[1];
char c[N];
struct node{
    char w,cvr;
    inline node():w('0'),cvr('0'){}
} T[N<<2];
inline void pushUp(int rt){
    T[rt].w=T[ls].w==T[rs].w?T[ls].w:'0';
}
inline void pushDown(int rt){
    T[ls].w=T[rs].w=T[rt].cvr;
    T[ls].cvr=T[rs].cvr=T[rt].cvr;
    T[rt].cvr='0';
}
void build(int rt,int l,int r){
    if(l==r){
        T[rt].w=c[l];
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushUp(rt);
}
void update(int rt,int l,int r,int L,int R,char k){
    if(l>=L && r<=R){
        T[rt].w=T[rt].cvr=k;
        return ;
    }
    if(T[rt].cvr!='0')
        pushDown(rt);
    int mid=l+r>>1;
    if(L<=mid)
        update(ls,l,mid,L,R,k);
    if(R>mid)
        update(rs,mid+1,r,L,R,k);
    pushUp(rt);
}
char query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R){
        return T[rt].w;
    }
    if(T[rt].cvr!='0')
        pushDown(rt);
    int mid=l+r>>1;
    if(R<=mid)
        return query(ls,l,mid,L,R);
    else if(L>mid)
        return query(rs,mid+1,r,L,R);
    else{
        char x=query(ls,l,mid,L,R),y=query(rs,mid+1,r,L,R);
        return x==y?x:'0';
    }
}
int main(){
    scanf("%d",&n);
    scanf("%s",c+1);
    build(1,1,n);
    scanf("%d",&k);
    for(;k--;){
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='A'){
            scanf("%s",p);
            update(1,1,n,l,r,p[0]);
        }
        else{
            if(query(1,1,n,l,r)=='0'){
                puts("No");
                continue;
            }
            if(l==1 || r==n){
                puts("Yes");
                continue;
            }
            if(query(1,1,n,l-1,l-1)!=query(1,1,n,r+1,r+1)){
                puts("Yes");
                continue;
            }
            puts("No");
        }
    }
    return 0;
}

添加新评论