fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1e5 + 5;
  5. const int BLOCK_SIZE = 320;
  6.  
  7. int n;
  8. long long a[MAX_N];
  9. long long bl[MAX_N / BLOCK_SIZE + 5];
  10. long long s[MAX_N / BLOCK_SIZE + 5];
  11.  
  12. void blockUpdate(int l, int r, int val){
  13.   for(int i = l; i <= r; i++)
  14.     bl[i] += val;
  15. }
  16.  
  17. void manualUpdate(int id, int l, int r, int val){
  18.   int L = id * BLOCK_SIZE;
  19.   int R = min(n - 1, (id + 1) * BLOCK_SIZE - 1);
  20.  
  21.   // cout << L << " " << R << endl;
  22.  
  23.   for(int i = L; i <= R; i++)
  24.     a[i] += bl[id];
  25.  
  26.   for(int i = l; i <= r; i++)
  27.     a[i] += val;
  28.  
  29.   s[id] = 0;
  30.   for(int i = L; i <= R; i++)
  31.     s[id] += a[i];
  32.  
  33.   bl[id] = 0;
  34. }
  35.  
  36. int main(){
  37.   ios_base::sync_with_stdio(0);
  38.   cin.tie(0);
  39.   cout.tie(0);
  40.  
  41.   int q;
  42.   cin >> n >> q;
  43.  
  44.   for(int i = 0; i < n; i++)
  45.     cin >> a[i],
  46.     s[i / BLOCK_SIZE] += a[i];
  47.  
  48.   while(q--){
  49.     int query;
  50.     cin >> query;
  51.  
  52.     // cout << query << "\n";
  53.  
  54.     if(query == 1){
  55.       int l, r, val;
  56.       cin >> l >> r >> val;
  57.  
  58.       // cout << query << " " << l << " " << r << " " << val << '\n';
  59.  
  60.       --l, --r;
  61.  
  62.       int blockL = l / BLOCK_SIZE;
  63.       int blockR = r / BLOCK_SIZE;
  64.  
  65.       if(blockL != blockR){
  66.         blockUpdate(blockL + 1, blockR - 1, val);
  67.         // L -> end block L
  68.         manualUpdate(blockL, l, (blockL + 1) * BLOCK_SIZE - 1, val);
  69.         // start block R -> R
  70.         manualUpdate(blockR, blockR * BLOCK_SIZE, r, val);
  71.       }
  72.       else
  73.         manualUpdate(blockR, l, r, val);
  74.     }
  75.  
  76.     else{
  77.       int l, r;
  78.       cin >> l >> r;
  79.       --l, --r;
  80.  
  81.       // cout << query << " " << l << " " << r << " " << '\n';
  82.  
  83.       int blockL = l / BLOCK_SIZE;
  84.       int blockR = r / BLOCK_SIZE;
  85.       long long ans = 0;
  86.  
  87.       if(blockL == blockR){
  88.         for(int i = l; i <= r; i++)
  89.           ans += a[i] + bl[blockL];
  90.         cout << ans << '\n';
  91.         continue;
  92.       }
  93.  
  94.       for(int i = blockL + 1; i <= blockR - 1; i++)
  95.         ans += s[i] + bl[i] * BLOCK_SIZE;
  96.       for(int i = l, endP = (blockL + 1) * BLOCK_SIZE - 1; i <= endP; i++)
  97.         ans += a[i] + bl[blockL];
  98.       for(int i = blockR * BLOCK_SIZE; i <= r; i++)
  99.         ans += a[i] + bl[blockR];
  100.  
  101.       cout << ans << '\n';
  102.     }
  103.   }
  104.  
  105.   return 0;
  106. }
Runtime error #stdin #stdout 0.01s 5536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/E52LoA
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!