fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long
  5. const int N=1e6+5,mod=1e9+7;
  6. ll base=31,pw[N+1],inv[N+1];
  7. ll powmod(ll a,ll b,ll m)
  8. {
  9.     ll ans=1;
  10.     while(b>0)
  11.     {
  12.         if(b&1)
  13.         {
  14.             ans=(ans*a)%m;
  15.         }
  16.         a=(a*a)%m;
  17.         b>>=1;
  18.     }
  19.     return ans;
  20. }
  21. int add(int a,int b)
  22. {
  23.     return((a%mod)+(b%mod))%mod;
  24. }
  25. int mul(int a,int b)
  26. {
  27.     return((a%mod)*(b%mod))%mod;
  28. }
  29. void init()
  30. {
  31.     pw[0]=inv[0]=1;
  32.     int temp1=powmod(base,mod-2,mod);
  33.     for(int i=1;i<N;i++)
  34.     {
  35.         pw[i]=(base*pw[i-1])%mod;
  36.         inv[i]=(inv[i-1]*temp1)%mod;
  37.     }
  38. }
  39. std::mt19937_64 rnd(std::chrono::system_clock::now().time_since_epoch().count());
  40. struct Treap{
  41.     struct Node{
  42.         int val,h=0;
  43.         int pri=rnd(),sz=1;
  44.         array<Node*,2>c={0,0};
  45.         Node(){}
  46.         Node(int k){
  47.             val=h=k;
  48.         }
  49.     };
  50.     Node*root=0;
  51.     int getSize(Node*t)
  52.     {
  53.         return t?t->sz:0;
  54.     }
  55.     int getHash(Node*t)
  56.     {
  57.         return t?t->h:0;
  58.     }
  59.     Treap(string&s)
  60.     {
  61.         for(int i=0;i<s.size();i++)
  62.         {
  63.             root=merge(root,new Node(s[i]-'a'+1));
  64. //            cout<<root->h<<'\n';
  65.         }
  66. //        print(root);
  67.     }
  68.     Node*fix(Node*t)
  69.     {
  70.         t->sz=getSize(t->c[0])+getSize(t->c[1])+1;
  71.         int x=mul(getHash(t->c[0]),pw[1]);
  72.         x=add(x,t->val);
  73.         x=mul(x,pw[getSize(t->c[1])]);
  74.         x=add(x,getHash(t->c[1]));
  75.         t->h=x;
  76. //        t->h=(((getHash(t->c[0])*base+t->val)%mod)*pw[getSize(t->c[1])]+getHash(t->c[1]))%mod;
  77.         return t;
  78.     }
  79.     array<Node*,2>split(Node*t,int k)
  80.     {
  81.         if(!t) return {0,0};
  82.         if(getSize(t->c[0])>=k)
  83.         {
  84.             auto ret=split(t->c[0],k);
  85.             t->c[0]=ret[1];
  86.             return {ret[0],fix(t)};
  87.         }
  88.         else
  89.         {
  90.             auto ret=split(t->c[1],k-getSize(t->c[0])-1);
  91.             t->c[1]=ret[0];
  92.             return {fix(t),ret[1]};
  93.         }
  94.     }
  95.     Node*merge(Node*u,Node*v)
  96.     {
  97.         if(!u||!v) return u?u:v;
  98.         if(u->pri>v->pri)
  99.         {
  100.             u->c[1]=merge(u->c[1],v);
  101.             return fix(u);
  102.         }
  103.         else
  104.         {
  105.             v->c[0]=merge(u,v->c[0]);
  106.             return fix(v);
  107.         }
  108.     }
  109.     void deleteRange(int l,int r)
  110.     {
  111.         auto a=split(root,l-1);
  112.         auto b=split(a[1],r-l+1);
  113.         root=merge(a[0],b[1]);
  114.     }
  115.     int getHash(int l,int r)
  116.     {
  117.         auto a=split(root,l-1);
  118.         auto b=split(a[1],r-l+1);
  119.         int ret=b[0]->h;
  120.         root=merge(a[0],merge(b[0],b[1]));
  121.         return ret;
  122.     }
  123.     void addChar(int pos,char c)
  124.     {
  125.         auto a=split(root,pos-1);
  126.         root=merge(merge(a[0],new Node(c-'a'+1)),a[1]);
  127.     }
  128.     void print(Node*t)
  129.     {
  130.         if(!t) return;
  131.         print(t->c[0]);
  132.         cout<<t->h<<' ';
  133.         print(t->c[1]);
  134.     }
  135. };
  136. int rev(int i,int n)
  137. {
  138.     return n-i+1;
  139. }
  140. signed main()
  141. {
  142.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  143.     init();
  144.     int n,q;cin>>n>>q;
  145.     string s;cin>>s;
  146.     string f=s;
  147.     reverse(f.begin(),f.end());
  148.     Treap a(s),b(f);
  149.     while(q--)
  150.     {
  151.         int op;cin>>op;
  152.         if(op==1)
  153.         {
  154.             int l,r;cin>>l>>r;
  155.             int l2=rev(l,n),r2=rev(r,n);
  156.             n-=(r-l+1);
  157.             a.deleteRange(l,r);
  158.             b.deleteRange(r2,l2);
  159.         }
  160.         else if(op==2)
  161.         {
  162.             int pos;char c;cin>>c>>pos;
  163.             a.addChar(pos,c);
  164.             b.addChar(rev(pos,n),c);
  165.             n++;
  166.         }
  167.         else
  168.         {
  169.             int l,r;cin>>l>>r;
  170.             int l2=rev(l,n),r2=rev(r,n);
  171. //            cout<<a.getHash(l,r)<<' '<<b.getHash(r2,l2)<<'\n';
  172.             if(a.getHash(l,r)==b.getHash(r2,l2))
  173.             {
  174.                 cout<<"yes\n";
  175.             }
  176.             else
  177.             {
  178.                 cout<<"no\n";
  179.             }
  180.         }
  181.     }
  182.     return 0;
  183. }
Success #stdin #stdout 0.01s 19192KB
comments (?)
stdin
copy 
4 4
aaaa
1 3 4
3 1 1
3 1 1
2 a 3
stdout
copy 
yes
yes
https://ideone.com/DhQfAu
language:
C++14 (gcc 8.3)
created:
14 days 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!