fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. struct FenwickTree {
  8.     vector<ll> bit;
  9.  
  10.     FenwickTree(int n) {
  11.         bit.assign(n + 1, 0);
  12.     }
  13.  
  14.     void add(int pos, ll val) {
  15.         for(++pos; pos < bit.size(); pos += pos & -pos)
  16.             bit[pos] += val;
  17.     }
  18.  
  19.     ll sum(int pos) {
  20.         ll res = 0;
  21.         for(++pos; pos > 0; pos -= pos & -pos)
  22.             res += bit[pos];
  23.         return res;
  24.     }
  25.  
  26.     ll rangeSum(int l, int r) {
  27.         return sum(r) - sum(l - 1);
  28.     }
  29. };
  30.  
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(nullptr);
  34.  
  35.     int n, q;
  36.     cin >> n >> q;
  37.  
  38.     vector<int> p(n + 1);
  39.     vector<int> pos(n + 1);
  40.     for(int i = 1; i <= n; i++) {
  41.         cin >> p[i];
  42.         pos[p[i]] = i;
  43.     }
  44.  
  45.     FenwickTree normal(n);
  46.     FenwickTree permuted(n);
  47.  
  48.     while(q--) {
  49.         int type;
  50.         cin >> type;
  51.  
  52.         if(type == 0) {
  53.             int l, r, c;
  54.             cin >> l >> r >> c;
  55.             for(int i = l; i <= r; i++) {
  56.                 normal.add(i - 1, c);
  57.             }
  58.         }
  59.         else if(type == 1) {
  60.             int l, r, c;
  61.             cin >> l >> r >> c;
  62.             for(int i = l; i <= r; i++) {
  63.                 permuted.add(p[i] - 1, c);
  64.             }
  65.         }
  66.         else if(type == 2) {
  67.             int l, r;
  68.             cin >> l >> r;
  69.             cout << normal.rangeSum(l - 1, r - 1) << "\n";
  70.         }
  71.         else {  // type == 3
  72.             int l, r;
  73.             cin >> l >> r;
  74.             ll sum = 0;
  75.             for(int i = l; i <= r; i++) {
  76.                 int idx = p[i] - 1;
  77.                 sum += normal.sum(idx) + permuted.sum(idx);
  78.             }
  79.             cout << sum << "\n";
  80.         }
  81.     }
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
5 6
3 1 5 4 2
0 2 4 2
1 2 4 3
2 3 4
0 2 5 1
3 2 4
3 1 3
stdout
copy 
4
37
31
https://ideone.com/udQZHH
language:
C++ (gcc 8.3)
created:
1 year 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!