fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. #define N 200005
  5. #define mod 1000000007
  6. ll suffix[200005]={0},p[N];
  7. ll prefix[200005]={0},inv[N];
  8. string s1,s;
  9. int n;
  10. ll pow(ll x,ll y)
  11. {
  12.     if(y==0)
  13.         return 1;
  14.     ll result=pow(x,y/2)%mod;
  15.     result=(result*result)%mod;
  16.     if(y&1==1)
  17.         result=(result*x)%mod;
  18.         return result;
  19. }
  20. void update(ll x,ll value,bool suff)
  21. {
  22.  
  23.     for(;x<N;x+=(x&(-x)))
  24.      {
  25.            if(suff)
  26.           suffix[x]=(suffix[x]+value)%mod;
  27.           else
  28.              prefix[x]=(prefix[x]+value)%mod;
  29.      }
  30.  
  31. }
  32. ll range(ll x,bool suff)
  33. {
  34. ll count=0;
  35.     for(;x>0;x-=(x&(-x)))
  36.      {
  37.          if(suff)
  38.           count=(count + suffix[x])%mod;
  39.           else
  40.              count=(count + prefix[x])%mod;
  41.      }
  42.      return count;
  43. }
  44. void hashing()
  45. {
  46. p[0]=1;
  47. inv[0]=1;
  48.     ll suff=0,pref=0;
  49.     ll val_pre=s[0]-'a'+1;
  50.     ll val_suf=s1[0]-'a'+1;
  51.     update(1,val_pre,0);
  52.     update(1,val_suf,1);
  53.     for(int i=1;i<n;i++)
  54.     {
  55.        p[i]=(p[i-1]*257)%mod;
  56.         val_pre=((s[i]-'a'+1)*p[i]+mod)%mod;
  57.         val_suf=((s1[i]-'a'+1)*p[i]+mod)%mod;
  58.      //   cout<<val_pre<<" "<<val_suf<<" ";
  59.         inv[i]=pow(p[i],mod-2);   // finding modulo  inverse
  60.         update(i+1,val_pre,0);
  61.     update(i+1,val_suf,1);
  62.     }
  63. }
  64. void query(int q)
  65. {
  66.  
  67.     while(q--)
  68.     {
  69.     int a;
  70.     cin>>a;
  71.     if(a==1)
  72.     {
  73.         int pos;
  74.         char k;
  75.         cin>>pos>>k;
  76.     ll val_pre=((s[pos-1]-'a'+1)*p[pos-1])%mod;
  77.     ll val_suf=((s1[n-pos]-'a'+1)*p[n-pos])%mod;
  78.     s1[n-pos]=k;
  79.     s[pos-1]=k;
  80.     update(pos,-1*val_pre,0);
  81.      update(n-pos+1,-1*val_suf,1);
  82.       val_pre=((s[pos-1]-'a'+1)*p[pos-1])%mod;
  83.      val_suf=((s1[n-pos]-'a'+1)*p[n-pos])%mod;
  84.      update(pos,val_pre,0);
  85.      update(n-pos+1,val_suf,1);
  86.  
  87.     }
  88.     else{
  89.         ll l,r;
  90.         cin>>l>>r;
  91.         ll val1=(((range(r,0)-range(l-1,0))*inv[l])%mod+mod)%mod;
  92.          ll val2=(((range(n-l+1,1)-range(n-r,1))*inv[n-r+1])% mod + mod)%mod;
  93.  //   cout<<s<<" "<<s1<<" "<<val1<<" "<<val2<<" ";
  94.          if(val1==val2)
  95.             cout<<"YES";
  96.             else
  97.          cout<<"NO";
  98.          cout<<endl;
  99.     }
  100.     }
  101. }
  102. int main()
  103. {
  104.     int q;
  105.     cin>>n>>q;
  106.     cin>>s;
  107.     s1=string(s.rbegin(),s.rend());
  108.   //cout<<s1<<" ";
  109.     hashing();
  110.     query(q);
  111.  
  112. }
  113.  
Runtime error #stdin #stdout 0.01s 7476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xab06J
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!