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