Advertisement
CSenshi

algo

Nov 11th, 2019
396
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5. #define NNN 100001
  6. #define ll long long
  7.  
  8. int T, N, Q, s, p, q, v;
  9. ll bit1[NNN + 1], bit2[NNN + 1];
  10.  
  11. void update(ll bit[], int i, ll val)
  12. {
  13.     while (i <= NNN)
  14.     {
  15.         bit[i] += val;
  16.         i += i & -i;
  17.     }
  18. }
  19.  
  20. ll query(ll bit[], int i)
  21. {
  22.     ll sum = 0;
  23.     while (i > 0)
  24.     {
  25.         sum += bit[i];
  26.         i -= i & -i;
  27.     }
  28.     return sum;
  29. }
  30.  
  31. int main()
  32. {
  33.     scanf("%d", &T);
  34.     while (T--)
  35.     {
  36.         scanf("%d %d", &N, &Q);
  37.         memset(bit1, 0, sizeof(bit1));
  38.         memset(bit2, 0, sizeof(bit2));
  39.         while (Q--)
  40.         {
  41.             scanf("%d ", &s);
  42.             if (s == 0)
  43.             {
  44.                 scanf("%d %d %d", &p, &q, &v);
  45.                 update(bit1, p, v);
  46.                 update(bit1, q + 1, -v);
  47.                 update(bit2, q + 1, (ll)v * q);
  48.                 update(bit2, p, -(ll)v * (p - 1));
  49.             }
  50.             else
  51.             {
  52.                 scanf("%d %d", &p, &q);
  53.                 ll ans = query(bit1, q) * q + query(bit2, q) -
  54.                          query(bit1, p - 1) * (p - 1) - query(bit2, p - 1);
  55.                 printf("%lld\n", ans);
  56.             }
  57.         }
  58.     }
  59.  
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement