fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1e5 + 5;
  5.  
  6. int n, q, T, arr[MAX];
  7. long long tree[MAX << 2], lazy[MAX << 2];
  8.  
  9. void Build(int id = 1, int L = 1, int R = n){
  10.     if(L == R){
  11.         tree[id] = arr[L];
  12.         return;
  13.     }
  14.     int mid = (L + R) >> 1;
  15.     Build(id << 1, L, mid);
  16.     Build(id << 1 | 1, mid + 1, R);
  17.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  18. }
  19.  
  20.  
  21. void Propagate(int id, int L, int mid, int R){
  22.     if(!lazy[id])
  23.         return;
  24.     lazy[id << 1] += lazy[id];
  25.     lazy[id << 1 | 1] += lazy[id];
  26.     tree[id << 1] += 1ll * (mid - L + 1) * lazy[id];
  27.     tree[id << 1 | 1] += 1ll * (R - mid) * lazy[id];
  28.     lazy[id] = 0;
  29. }
  30.  
  31. void UpdateSqrt(int st, int en, int id = 1, int L = 1, int R = n){
  32.     if(tree[id] == R - L + 1)
  33.         return;
  34.     if(L == R){
  35.         tree[id] = sqrt(tree[id]);
  36.         return;
  37.     }
  38.     int mid = (L + R) >> 1;
  39.     Propagate(id, L, mid, R);
  40.     if(st <= mid)
  41.         UpdateSqrt(st, en, id << 1, L, mid);
  42.     if(en > mid)
  43.         UpdateSqrt(st, en, id << 1 | 1, mid + 1, R);
  44.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  45. }
  46.  
  47. void UpdateRange(int st, int en, int val, int id = 1, int L = 1, int R = n){
  48.     if(st > R || L > en)
  49.         return;
  50.     if(st <= L && R <= en){
  51.         tree[id] += 1ll * (R - L  + 1) * val;
  52.         lazy[id] += val;
  53.         return;
  54.     }
  55.     int mid = (L + R) >> 1;
  56.     Propagate(id, L, mid, R);
  57.     UpdateRange(st, en, val, id << 1, L, mid);
  58.     UpdateRange(st, en, val, id << 1 | 1, mid + 1, R);
  59.     tree[id] = tree[id << 1] + tree[id << 1 | 1];
  60. }
  61.  
  62. long long Query(int st, int en, int id = 1, int L = 1, int R = n){
  63.     if(st <= L && R <= en)
  64.         return tree[id];
  65.     int mid = (L + R) >> 1;
  66.     Propagate(id, L, mid, R);
  67.     if(en <= mid)
  68.         return Query(st, en, id << 1, L, mid);
  69.     if(st > mid)
  70.         return Query(st, en, id << 1 | 1, mid + 1, R);
  71.     return Query(st, en, id << 1, L, mid) + Query(st, en, id << 1 | 1, mid + 1, R);
  72. }
  73.  
  74. int main(){
  75.  
  76.     scanf("%d", &T);
  77.     while(T--) {
  78.         memset(lazy, 0, sizeof lazy);
  79.         memset(tree, 0, sizeof tree);
  80.         scanf("%d %d", &n, &q);
  81.         for (int i = 1; i <= n; i++)
  82.             scanf("%d", arr + i);
  83.         Build();
  84.         while (q--){
  85.             int t, L, R, x;
  86.             scanf("%d %d %d", &t, &L, &R);
  87.             if (t == 1)
  88.                 UpdateSqrt(L, R);
  89.             else if(t == 2)
  90.                 printf("%lld\n", Query(L, R));
  91.             else if(t == 3){
  92.                 scanf("%d", &x);
  93.                 UpdateRange(L, R, x);
  94.             }
  95.         }
  96.     }
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0s 21880KB
comments (?)
stdin
copy 
1
10 7
1 5 123 53 12 2901 12 1234 657 3419
2 3 7
3 5 8 1
1 2 4
3 1 6 1000
2 1 10
2 2 8
1 3 5
stdout
copy 
3101
14260
9183
https://ideone.com/3s2FQk
language:
C++14 (gcc 8.3)
created:
7 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!