C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 3424K, 提交时间: 2019-04-14 15:41:47

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+50;
// const ull seed=19260817;
const ull seed=27;
char s[N];
int n,m;
int o,l,r;
char q[2];
ull p[N];
void init(){
    p[0]=1ll;
    for(int i=1;i<N;i++){
        p[i]=p[i-1]*seed;
    }
}
ull h[N],rh[N];
int lowbit(int x){
    return x&(-x);
}
void add(int i,ull x){
    while(i<=n){
        h[i]+=x;
        i+=lowbit(i);
    }
}
ull sum(int i){
    ull ans=0;
    while(i>0){
        ans+=h[i];
        i-=lowbit(i);
    }
    return ans;
}
void add2(int i,ull x){
    while(i<=n){
        rh[i]+=x;
        i+=lowbit(i);
    }
}
ull sum2(int i){
    ull ans=0;
    while(i>0){
        ans+=rh[i];
        i-=lowbit(i);
    }
    return ans;
}
int main(void){
    init();
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    ull hs=0;
    ull rhs=0;
    for(int i=1;i<=n;i++){
        //printf("%c %c\n",s[i],s[n-i+1]);
        hs=((s[i]-'a')*p[i-1]);
        rhs=((s[n-i+1]-'a')*p[i-1]);
        //cout << " " << (s[i]-'0') << " " << hs << " " << (s[n-i+1]-'0') << " " <<  rhs << endl;
        add(i,hs);
        add2(i,rhs);
    }
    // while(~scanf("%d%d",&l,&r)){
    //     cout <<"*** " << sum(r) <<" " << sum(l-1) << " " << p[r-l+1] << endl;
    //     cout <<"*** " << sum2(r) <<" " << sum2(l-1) << " " << p[r-l+1] << endl;
    //     ull hh1=sum(r)-sum(l-1);
    //     ull rh2=sum2(r)-sum2(l-1);
    //     cout << hh1 <<" " << rh2 << endl;
    // }
    while(m--){
        scanf("%d",&o);
        if(o==1){
            scanf("%d %s",&l,q);
            ull b=(q[0]-s[l])*1ll;
            // cout << "b " << b << endl; 
            add(l,b*p[l-1]);
            add2(n-l+1,b*p[n-l]);
            s[l]=q[0];
        }else{
            scanf("%d%d",&l,&r);
            ull hh1=sum(r)-sum(l-1);
            ull rh2=sum2(r)-sum2(l-1);
            // cout << hh1 <<" " << rh2 << endl;
            if(hh1==rh2){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 62ms, 内存消耗: 1276K, 提交时间: 2019-04-15 20:44:54

#include <iostream>
#include <algorithm>
 
#define maxn 100005
using namespace std;
 
int n,m,c[maxn],cmd,l,r;
char c1[maxn],c2[maxn],ch;

int lowbit(int x)
{
    return x&(-x);
}

void add(int pos,int d)
{
    while(pos<=n)
    {
        c[pos]+=d;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int ans=0;
    while(pos)
    {
        ans+=c[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    scanf("%s",c1+1);
    for(int i=1;i<=n;++i)
        c2[i]=c1[n-i+1];
    for(int i=1;i<=n;++i)
        if(c1[i]!=c2[i])
            add(i,1);
    for(int i=0;i<m;++i)
    {
        scanf("%d",&cmd);
        switch (cmd)
        {
        case 1:
            scanf("%d %c",&l,&ch);
            if(c1[l]!=c2[l])
                add(l,-1),add(n-l+1,-1);
            if(ch!=c2[l])
                add(l,1),add(n-l+1,1);
            c1[l]=c2[n-l+1]=ch;
            break;
        case 2:
            scanf("%d %d",&l,&r);
            int ans=query(r)-query(l-1);
            printf(ans?"NO\n":"YES\n");
            break;
        }
    }
    return 0;
}