RT，由于我忘记了标准的 ODT 写法，于是自己弄了一个奇怪的东西。

具体来说，每次推平的时候把中间的整连续段全部删掉，然后断掉两边的散段，修改，再处理两端，使得 set 里面总是全部都是极长连续段。

这样之后询问不难做到严格 $\mathcal O(\log)$。

没有经过任何特意卡常和剪枝之类的优化就把题过了，O2 不开也能过（开 O2 1s，不开 2s）。

我感觉复杂度挺对的，但是又很怪。想问一下这样做复杂度是对的吗？

代码：

//Author:Leftist / Shunpower
//Spade Su & Griffin BAO
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld long double
#define il inline
#define ptc putchar
//Quickly power: ll d=qpow(b,p>>1,k);
//Segment Tree: Memory Limit Excceed
//Segment Tree: Modify()->Pushdown()
//Mod: +M, %M, define int ll
//Mod: Don't use 998244353 instead of 1e9+7 and so on
//Don't solve a problem for too long time.
using namespace std;
const int N=5e5+10;
namespace Shun{
    int lowbit(int x){
        return x&-x;
    }
    template <typename T>
    inline void read(T &x){
       T s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;
            }
            ch=getchar();
        }
       while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
       }
       x=s*w;
    }
    template <typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace Shun;
int n;
char c[N];
struct node{
    int l,r;
    char v;
    bool operator<(const node &p) const{
        return l<p.l;
    }
};
set <node> s;
int q;
void modify(int l,int r,char c){
    auto st=s.upper_bound({l,0,0});
    st--;
    auto ed=st;
    while(r>ed->r){
        ed++;
    }
    node L=(*st);
    node R=(*ed);
    ed++;
    if(l==L.l&&st!=s.begin()){
        st--;
        if(st->v==c){
            l=st->l;
        }
        else{
            st++;
        }
    }
    if(r==R.r&&ed!=s.end()){
        if(ed->v==c){
            r=ed->r;
            ed++;
        }
    }
    s.erase(st,ed);
    if(L.v==c&&l>L.l) l=L.l;
    if(R.v==c&&r<R.r) r=R.r;
    if(l>L.l) s.insert({L.l,l-1,L.v});
    if(r<R.r) s.insert({r+1,R.r,R.v});
    s.insert({l,r,c});
}
bool check(int l,int r){
    auto st=s.upper_bound({l,0,0});
    st--;
    auto S=*st;
    if(r>S.r){
        return 0;
    }
    if(l==1||r==n){
        return 1;
    }
    char pre,nxt;
    if(l==S.l){
        st--;
        pre=st->v;
        st++;
    }
    else{
        pre=S.v;
    }
    if(r==S.r){
        st++;
        nxt=st->v;
    }
    else{
        nxt=S.v;
    }
    return pre!=nxt;
}
int main(){
#ifdef Griffin
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n;
    fr1(i,1,n){
        cin>>c[i];
    }
    int len=0;
    fr1(i,1,n){
        if(c[i]!=c[i+1]){
            len++;
            s.insert({i-len+1,i,c[i]});
            len=0;
        }
        else{
            len++;
        }
    }
    cin>>q;
    while(q--){
        // for(auto it:s){
        //     cout<<it.l<<" "<<it.r<<" "<<it.v<<endl;
        // }
        char op;
        int x,y;
        char c;
        cin>>op>>x>>y;
        if(op=='A'){
            cin>>c;
            modify(x,y,c);
        }
        else{
            cout<<(check(x,y)?"Yes":"No")<<'\n';
        }
    }
    ET;
}
//ETERNAL LOVE FOR Zhang Junhao, Mu Zhicheng and Zuo Hang.
//ALL FOR Zhang Junhao.