求调(无法输出)
查看原帖
求调(无法输出)
563127
Jiangyx1028楼主2024/8/7 08:53
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
char s[2*N];
struct seg{
    int l,r,sum;
}t[26][N*4];
inline void build(seg t[],int p,int l,int r,int c){
    if(l==r){
        t[p].sum=s[l] == c + 'a';
        return ;
    }
    int mid=(l+r) >>1;
    build(t,p << 1,l,mid,c);
    build(t,(p << 1) | 1,mid+1,r,c);
    t[p].sum=t[p << 1].sum+t[(p << 1 )| 1].sum;
}
inline void change(seg t[],int p,int x,int v){
    if(x>n)return ;
    if(t[p].l==t[p].r){
        t[p].sum=v;
        return ;
    }
    int mid=(t[p].l+t[p].r) >>1;
    if(x<=mid)change(t,p << 1,x,v);
    else change(t,(p << 1) | 1,x,v);
    t[p].sum=t[p << 1].sum+t[(p << 1) | 1].sum;
}
inline int query(seg t[],int p,int l,int r){
    if (l<=t[p].l && t[p].r<=r)return t[p].sum;
    int mid= (t[p].l+t[p].r) >>1,res=0;
    if(l<=mid)res+=query(t,p << 1,l,r);
    if(r>mid)res+=query(t,(p << 1) | 1,l,r);
    return res;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=0;i<26;i++)
        build(t[i],1,1,n,i);
    // for(int i=0;i<26;i++)
    //     printf("%d",t[i][1].sum);
    scanf("%d",&m);
    while(m--){
        int op;scanf("%d",&op);
        if(op==1){
            int x;
            char c;
            cin>>x>>c;
            change(t[s[x]-'a'],1,x,0);
            change(t[c-'a'],1,x,1);
            s[x]=c;
        }else if(op==2){
            int l,r;scanf("%d%d",&l,&r);
            bool flag=true;
            int now=l,cnt1,cnt2;
            int head=30,tail=-1;
            for(int i=0;i<26;i++)
                if(query(t[i],1,l,r))
                    head=min(head,i),tail=max(tail,i);
            for(int i=0;i<26;i++){
                if(flag)break;
                if( !query(t[i],1,l,r) && (i>=head && i<=tail) && query(t[i],1,1,n))flag=1;
                if(i==head || i==tail)cnt1=query(t[i],1,l,r);
                else cnt1=query(t[i],1,1,n);
                cnt2=query(t[i],1,now,now+cnt1-1);
                now+=cnt1;
                if(cnt1!=cnt2)flag=1;
            }
            if(flag)puts("No");
            else puts("Yes");
        }
    }
    return 0;
}
/*

*/
2024/8/7 08:53
加载中...