fork(3) download
copy 
  1. #include<iostream>
  2. #include<math.h>
  3. #include<algorithm>
  4. #include<stdio.h>
  5. #include<map>
  6. #include<vector>
  7. #include<set>
  8. #include<iomanip>
  9. #define F first
  10. #define S second
  11. #define P system("PAUSE");
  12. #define H return 0;
  13. #define pb push_back
  14. using namespace std;
  15.  
  16. const long long A=100000000000000LL,N=228228;
  17. const long long os[2]={11,13};
  18. const long long MOD[2]={1000000007,1073676287};
  19.  
  20. string a;
  21. long long t[2][2][N*4],st[2][N],dp[2][N],type,l,r,d,i,j,n,m[2];
  22.  
  23. long long Get(int k,int l,int r){
  24.     l--,r--;
  25.     if(!l)return dp[k][r];else return ((dp[k][r]-dp[k][l-1])%MOD[k]+MOD[k])%MOD[k];
  26. }
  27.  
  28. void push(int k,int v,int l,int r){
  29.     if(!t[k][1][v])return;
  30.     int mid=(l+r)/2;
  31.     t[k][0][v*2]=(t[k][1][v]*Get(k,l,mid))%MOD[k];
  32.     t[k][0][v*2+1]=(t[k][1][v]*Get(k,mid+1,r))%MOD[k];
  33.     t[k][1][v*2]=t[k][1][v*2+1]=t[k][1][v];
  34.     t[k][1][v]=0;
  35. }
  36.  
  37. void modi(int k,int v,int l,int r,int _l,int _r,long long g){
  38.     if(_l>_r)return;
  39.     if(l==_l && r==_r){
  40.         t[k][0][v]=(g*Get(k,l,r))%MOD[k],t[k][1][v]=g;
  41.         return;
  42.     }
  43.     int mid=(l+r)/2;
  44.     push(k,v,l,r);
  45.     modi(k,v*2,l,mid,_l,min(_r,mid),g),modi(k,v*2+1,mid+1,r,max(mid+1,_l),_r,g);
  46.     t[k][0][v]=t[k][0][v*2]+t[k][0][v*2+1];
  47. }
  48.  
  49. long long get(int k,int v,int l,int r,int _l,int _r){
  50.     if(_l>_r)return 0;
  51.     if(l==_l && r==_r)return t[k][0][v];
  52.     push(k,v,l,r);
  53.     int mid=(l+r)/2;
  54.     return (get(k,v*2,l,mid,_l,min(mid,_r))+get(k,v*2+1,mid+1,r,max(mid+1,_l),_r))%MOD[k];
  55. }
  56.  
  57. int main(){
  58.     cin>>n>>m[0]>>m[1];
  59.     cin>>a;
  60.     for(d=0;d<2;d++){
  61.         st[d][0]=dp[d][0]=1;
  62.         for(i=1;i<n;i++)st[d][i]=st[d][i-1]*os[d],st[d][i]%=MOD[d],dp[d][i]=dp[d][i-1]+st[d][i],dp[d][i]%=MOD[d];
  63.         for(i=0;i<n;i++)modi(d,1,1,n,i+1,i+1,a[i]-'0'+1);
  64.     }
  65.     m[0]+=m[1];
  66.     while(m[0]--){
  67.         scanf("%d%d%d%d",&type,&l,&r,&d);
  68.         if(type==1){
  69.             for(i=0;i<2;i++)modi(i,1,1,n,l,r,d+1);
  70.         }else{
  71.             if(l==r || (((get(0,1,1,n,l,r-d)*st[0][d])%MOD[0]==get(0,1,1,n,l+d,r))&&
  72.                 ((get(1,1,1,n,l,r-d)*st[1][d])%MOD[1]==get(1,1,1,n,l+d,r))))puts("YES");else puts("NO");
  73.         }
  74.     }
  75. }
Success #stdin #stdout 0s 39128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uXmsPS
language:
C++14 (gcc 8.3)
created:
9 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!