开O2CE？

kradcigam @ 2020-06-06 11:04:16

by SmokedFish @ 2020-06-06 11:05:27

代码？

by SmokedFish @ 2020-06-06 11:05:34

@赵海鲲

by sweet_carrot @ 2020-06-06 11:05:49

c，lznb

by sweet_carrot @ 2020-06-06 11:06:13

（接下去哇quq）

by xiyihan @ 2020-06-06 11:06:34

Undefined behavior??

by kradcigam @ 2020-06-06 11:06:45

代码：

// Problem : P4979 矿洞：坍塌
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P4979
// Memory Limit : 250 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define ls num<<1
#define rs num<<1|1
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
const int MAXN=5e5+10;
int a[MAXN],L,R,S,n;
struct Line_Tree{
    struct Tree{
        int l,r,lazy;
        bool s[3];
    }t[MAXN<<2];
    void pushup(int num){
        for(int i=1;i<=3;i++)t[num].s[i]=(t[ls].s[i]&&t[rs].s[i]);
    }
    void down1(int num){
        t[num].lazy=1;
        t[num].s[1]=1;
        t[num].s[2]=0;
        t[num].s[3]=0;
    }
    void down2(int num){
        t[num].lazy=2;
        t[num].s[1]=0;
        t[num].s[2]=1;
        t[num].s[3]=0;
    }
    void down3(int num){
        t[num].lazy=3;
        t[num].s[1]=0;
        t[num].s[2]=0;
        t[num].s[3]=1;
    }
    void pushdown(int num){
        if(t[num].lazy==1)down1(ls),down1(rs);
        if(t[num].lazy==2)down2(ls),down2(rs);
        if(t[num].lazy==3)down3(ls),down3(rs);
        t[num].lazy=0;
    }
    void build(int num,int l,int r){
        t[num].l=l;t[num].r=r;t[num].lazy=0;
        if(l==r){
            for(int i=1;i<=3;i++)t[num].s[i]=(a[l]==i);
            // cout<<l<<" "<<t[num].s[1]<<" "<<t[num].s[2]<<" "<<t[num].s[3]<<" "<<a[l]<<endl;
            return;
        }int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(num);
    }
    void change(int num){
        if(L<=t[num].l&&t[num].r<=R){
            if(S==1)down1(num);
            if(S==2)down2(num);
            if(S==3)down3(num);
            return;
        }pushdown(num);
        if(t[ls].r>=L)change(ls);
        if(t[rs].l<=R)change(rs);
        pushup(num);
    }
    bool query1(int num,int f){
        if(L<=t[num].l&&t[num].r<=R){
            // cerr<<t[num].l<<" "<<t[num].r<<" "<<char(48+f)<<" "<<t[num].s[f]<<endl;
            return t[num].s[f];
        }
        pushdown(num);
        if(t[ls].r<L)return query1(rs,f);
        if(t[rs].l>R)return query1(ls,f);
        return (query1(ls,f)&&query1(rs,f));
    }
    int query2(int num,int S){
        if(t[num].l==t[num].r){
            for(int i=1;i<=3;i++)
                if(t[num].s[i])return i;
        }pushdown(num);
        if(t[ls].r>=S)return query2(ls,S);
        if(t[rs].l<=S)return query2(rs,S);
    }
}T;
int init(){
    read(n);
    for(int i=1;i<=n;i++){
        char ch=getchar();
        for(;ch!='A'&&ch!='B'&&ch!='C';ch=getchar());
        a[i]=ch-64;
    }T.build(1,1,n);
    return 0;
}
int work2(){
    if(L==1||R==n){puts("Yes");return 0;}
    if(T.query2(1,L-1)!=T.query2(1,R+1))puts("Yes");
    else puts("No");
    return 0;
}
int work(){
    char ch=getchar();for(;ch!='A'&&ch!='B';ch=getchar());
    if(ch=='A'){
        read(L);read(R);ch=getchar();for(;ch!='A'&&ch!='B'&&ch!='C';ch=getchar());S=ch-64;
        T.change(1);
    }else{
        read(L);read(R);
        for(int i=1;i<=3;i++)
            if(T.query1(1,i)){work2();return 0;}
        puts("No");
    }
    return 0;
}
int main(){
    init();
    int T;read(T);
    while(T--){
        //memset
        work();
    }
    return 0;
}
/*
15
AACBBABBBCCCBBB
4
B 4 5
B 5 5
A 9 12 C
B 10 12
*/

by kradcigam @ 2020-06-06 11:06:52

@DS优化线段树

by zhanghzqwq @ 2020-06-06 11:07:01

emm

by dehsirehC @ 2020-06-06 11:07:59

灵 异 事 件

by kradcigam @ 2020-06-06 11:09:12

好，我不卡O2卡常卡过去了