fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define vll vector<ll >
  6. #define vvi vector<vi >
  7. #define pb push_back
  8.  
  9. const ll mod = 998244353;
  10. const ll g = 3;
  11. const int blk =9000;
  12. int bit[2][800000+100];
  13. const int N = 200005;
  14. ll a[N];
  15. ll pa[N],pb[N];
  16. vector<ll> aa,b,b1;
  17. vector<int> v;
  18. int maxn, n,q,LG;
  19.  
  20. ll powr(ll a, ll b, ll mod)
  21. {
  22.     ll x = 1;
  23.     a %= mod;
  24.     while(b)
  25.     {
  26.         if(b&1)
  27.             x = (x*a)%mod;
  28.         a = (a*a)%mod;
  29.         b >>= 1;
  30.     }
  31.     return x;
  32. }
  33. ll inv(ll a, ll mod)
  34. {
  35.     return powr(a,mod-2,mod);
  36. }
  37. class NTT{
  38.  
  39.     ll p,g,n,logn;
  40. public:
  41.     NTT(ll P, ll G, ll LOGN)    
  42.     {
  43.         p = P;
  44.         ll g1 = G;
  45.         logn = LOGN;
  46.         n = (1<<LOGN);
  47.         assert((p-1)%n == 0);
  48.         g = powr(g1,(p-1)>>logn,p);
  49.     }
  50.  
  51.     int bitrevcopy(int i)
  52.     {   
  53.  
  54.         if(bit[LG==logn][i])return bit[LG==logn][i];
  55.  
  56.         int ret = 0;
  57.         for(int j = 0;j<logn;j++)
  58.        {
  59.             if(i&(1<<j))
  60.                 ret|=(1<<(logn-1-j));
  61.         }
  62.         return bit[LG==logn][i] = ret;
  63.     }
  64.     void fft(vll& a, bool invert)
  65.     {   
  66.         ll mod = p;
  67.         for(int i = 0;i<n;i++)
  68.         {
  69.  
  70.             int br = bitrevcopy(i);
  71.             if(i<br)
  72.                 swap(a[i],a[br]);
  73.         }
  74.         for(int i = 1;i<=logn;i++)
  75.         {
  76.             ll mul = powr(g,1<<(logn-i),p);
  77.             if(invert)
  78.                 mul = inv(mul,p);
  79.             int add = (1<<i);
  80.             for(int k = 0;k<n;k+=add)
  81.             {
  82.                 ll w = 1;
  83.                 ll lim = (add>>1);
  84.                 for(int j = 0;j<lim;j++)
  85.                 {
  86.  
  87.                     ll u = (w*a[k+j+lim])%p, v = a[k+j];
  88.                     a[k+j] = u+v;
  89.                     if(a[k+j]>=p)
  90.                         a[k+j] -= p;
  91.                     a[k+j+lim] = v-u;
  92.                     if(a[k+j+lim]<0)
  93.                         a[k+j+lim]+=p;
  94.                     w = (w*mul)%p;
  95.                 }
  96.             }
  97.         }
  98.         if(invert){
  99.             ll _inv = inv(n,p);
  100.             for(int i = 0;i<n;i++){
  101.  
  102.                 a[i] = (a[i]*_inv)%p;
  103.             }
  104.         }
  105.     }
  106. };
  107. void NTT_mul(vll& a)
  108. {
  109.     int _sz = a.size()+n-1;
  110.  
  111.     int LOGN = 0;
  112.     while((1<<LOGN) < _sz)
  113.         LOGN++;
  114.     ll N = (1<<LOGN);
  115.     a.resize(N);
  116.     NTT fft1 = NTT(mod,g,LOGN);
  117.     fft1.fft(a,false);
  118.  
  119.     if(LG == LOGN)
  120.         {
  121.             for(int i = 0;i<N;i++)
  122.            a[i] = (a[i]*b[i])%mod;
  123.         }
  124.     else
  125.         {
  126.             for(int i = 0;i<N;i++)
  127.            a[i] = (a[i]*b1[i])%mod;
  128.         }
  129.  
  130.     fft1.fft(a,true);
  131.  
  132.     for(int i = 0;i<=n;i++)
  133.         a[i] %= mod;
  134. }   
  135.  
  136. void doit(){
  137.  
  138.     while((1<<LG)<n)LG++;
  139.     b.resize(1<<LG);
  140.     b1.resize(1<<(LG+1));
  141.     NTT fft1 = NTT(mod,g,LG);
  142.     NTT fft2 = NTT(mod,g,LG+1);
  143.     fft1.fft(b,false);
  144.     fft2.fft(b1,false);
  145. }
  146.  
  147. int main()
  148. {
  149.     clock_t clk = clock();
  150.     //freopen ("t10.txt","r",stdin);
  151.     //freopen ("o10.txt","w",stdout);
  152.     scanf("%d %d",&n,&q);
  153.     for(int i=1;i<=n;i++)
  154.     {
  155.         scanf("%lld",&a[i]);
  156.         pa[i] = (pa[i-1] + a[i]);
  157.     }
  158.     b.resize(n);
  159.     b1.resize(n);
  160.  
  161.     for(int i=0;i<n;i++)
  162.     {
  163.         scanf("%lld",&b[i]);
  164.         b1[i]=b[i];
  165.         pb[i+1] = (pb[i] + b[i]);
  166.     }
  167.     doit();
  168.     for(int i=1;i<=q;i++)
  169.     {
  170.         int t,l,r;
  171.         scanf("%d %d",&t,&l);
  172.         if(t==1)
  173.         {
  174.             v.pb(l);
  175.         }
  176.         else
  177.         {
  178.             scanf("%d",&r);
  179.             ll ans = pa[r]-pa[l-1];
  180.             for(int j=0; j<v.size();j++)
  181.             {   
  182.                 int x =v[j];
  183.                 if(x<=l)
  184.                     ans = (ans + pb[r-x+1]-pb[l-x]);
  185.                 else if(x<=r)
  186.                     ans = (ans + pb[r-x+1]);
  187.             }
  188.             printf("%lld\n",ans);
  189.         }
  190.         if(v.size() == blk)
  191.         {
  192.             aa.clear();
  193.             aa.resize(n);
  194.             maxn =0;
  195.             for(int x: v)
  196.             {
  197.                 maxn =max(maxn,x);
  198.                 aa[x-1]++;
  199.             }
  200.             aa.resize(maxn);
  201.             NTT_mul(aa);
  202.             for(int i=0;i<n;i++)
  203.             {
  204.  
  205.                 a[i+1] = (a[i+1] + aa[i]);
  206.                 pa[i+1] = (pa[i] + a[i+1]);
  207.             }
  208.             v.clear();
  209.         }
  210.     }
  211.     //cerr<<(float)(clock()-clk)/CLOCKS_PER_SEC<<endl;
  212.     return 0;
  213. }
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
4 3
1 2 1 4
2 1 2 3
1 2
2 1 1
2 2 4
stdout
copy 
1
12
https://ideone.com/SCeO76
language:
C++14 (gcc 8.3)
created:
6 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!