fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1e5 + 5;
  7.  
  8. int A[N], P[N], P_map[N];
  9. vector<int> segTree(4 * N);
  10.  
  11. void build(int node, int start, int end) {
  12.     if (start == end) {
  13.         segTree[node] = A[start];
  14.     } else {
  15.         int mid = (start + end) / 2;
  16.         build(2 * node, start, mid);
  17.         build(2 * node + 1, mid + 1, end);
  18.         segTree[node] = segTree[2 * node] + segTree[2 * node + 1];
  19.     }
  20. }
  21.  
  22. void update(int node, int start, int end, int idx, int val) {
  23.     if (start == end) {
  24.         segTree[node] += val;
  25.     } else {
  26.         int mid = (start + end) / 2;
  27.         if (idx <= mid) {
  28.             update(2 * node, start, mid, idx, val);
  29.         } else {
  30.             update(2 * node + 1, mid + 1, end, idx, val);
  31.         }
  32.         segTree[node] = segTree[2 * node] + segTree[2 * node + 1];
  33.     }
  34. }
  35.  
  36. int query(int node, int start, int end, int l, int r) {
  37.     if (r < start || end < l) {
  38.         return 0;
  39.     }
  40.     if (l <= start && end <= r) {
  41.         return segTree[node];
  42.     }
  43.     int mid = (start + end) / 2;
  44.     int leftSum = query(2 * node, start, mid, l, r);
  45.     int rightSum = query(2 * node + 1, mid + 1, end, l, r);
  46.     return leftSum + rightSum;
  47. }
  48.  
  49. int main() {
  50.     int N, Q;
  51.     cin >> N >> Q;
  52.  
  53.     // Initialize A to 0
  54.     for (int i = 1; i <= N; i++) {
  55.         A[i] = 0;
  56.     }
  57.  
  58.     // Read the permutation P
  59.     for (int i = 1; i <= N; i++) {
  60.         cin >> P[i];
  61.         P_map[P[i]] = i;
  62.     }
  63.  
  64.     // Build the Segment Tree
  65.     build(1, 1, N);
  66.  
  67.     while (Q--) {
  68.         int type;
  69.         cin >> type;
  70.  
  71.         if (type == 0 || type == 1) {
  72.             int l, r, c;
  73.             cin >> l >> r >> c;
  74.  
  75.             if (type == 0) {
  76.                 // Update the range [l, r] in A
  77.                 for (int i = l; i <= r; i++) {
  78.                     update(1, 1, N, i, c);
  79.                 }
  80.             } else {
  81.                 // Update the range [P[l], P[r]] in A
  82.                 for (int i = l; i <= r; i++) {
  83.                     update(1, 1, N, P_map[i], c);
  84.                 }
  85.             }
  86.         } else if (type == 2 || type == 3) {
  87.             int l, r;
  88.             cin >> l >> r;
  89.  
  90.             if (type == 2) {
  91.                 // Query the sum of the range [l, r] in A
  92.                 cout << query(1, 1, N, l, r) << endl;
  93.             } else {
  94.                 // Query the sum of the range [P[l], P[r]] in A
  95.                 int sum = 0;
  96.                 for (int i = l; i <= r; i++) {
  97.                     sum += query(1, 1, N, P_map[i], P_map[i]);
  98.                 }
  99.                 cout << sum << endl;
  100.             }
  101.         }
  102.     }
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0.01s 5276KB
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 
7
13
10
https://ideone.com/najZFQ
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!