fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. class FenwickTree {
  8. private:
  9.     vector<ll> bit;
  10.     int n;
  11.  
  12. public:
  13.     FenwickTree(int size) : n(size) {
  14.         bit.resize(n + 1, 0);
  15.     }
  16.  
  17.     void add(int idx, ll val) {
  18.         idx++;
  19.         while (idx <= n) {
  20.             bit[idx] += val;
  21.             idx += idx & (-idx);
  22.         }
  23.     }
  24.  
  25.     ll sum(int idx) {
  26.         idx++;
  27.         ll res = 0;
  28.         while (idx > 0) {
  29.             res += bit[idx];
  30.             idx -= idx & (-idx);
  31.         }
  32.         return res;
  33.     }
  34.  
  35.     ll rangeSum(int l, int r) {
  36.         return sum(r) - (l > 0 ? sum(l - 1) : 0);
  37.     }
  38. };
  39.  
  40. int main() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.  
  44.     int n, q;
  45.     cin >> n >> q;
  46.  
  47.     vector<int> p(n);
  48.     vector<int> pos(n + 1);  // Position de chaque élément dans p
  49.     for (int i = 0; i < n; i++) {
  50.         cin >> p[i];
  51.         pos[p[i]] = i;
  52.     }
  53.  
  54.     FenwickTree ft1(n);  // Pour les mises à jour de type 0
  55.     FenwickTree ft2(n);  // Pour les mises à jour de type 1
  56.  
  57.     while (q--) {
  58.         int type;
  59.         cin >> type;
  60.  
  61.         if (type == 0) {
  62.             int l, r, x;
  63.             cin >> l >> r >> x;
  64.             l--; r--;
  65.             ft1.add(l, x);
  66.             ft1.add(r + 1, -x);
  67.         }
  68.         else if (type == 1) {
  69.             int l, r, x;
  70.             cin >> l >> r >> x;
  71.             l--; r--;
  72.             ft2.add(l, x);
  73.             ft2.add(r + 1, -x);
  74.         }
  75.         else if (type == 2) {
  76.             int l, r;
  77.             cin >> l >> r;
  78.             l--; r--;
  79.             cout << ft1.rangeSum(l, r) << "\n";
  80.         }
  81.         else {  // type == 3
  82.             int l, r;
  83.             cin >> l >> r;
  84.             l--; r--;
  85.             ll result = 0;
  86.             for (int i = l; i <= r; i++) {
  87.                 int actualPos = pos[i + 1];
  88.                 result += ft1.rangeSum(actualPos, actualPos) + ft2.rangeSum(i, i);
  89.             }
  90.             cout << result << "\n";
  91.         }
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5292KB
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 
0
1
4
https://ideone.com/WogYT2
language:
C++ (gcc 8.3)
created:
5 days 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!