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.     // ... (same as before)
  13. }
  14.  
  15. void update(int node, int start, int end, int idx, int val) {
  16.     // ... (same as before)
  17. }
  18.  
  19. int query(int node, int start, int end, int l, int r) {
  20.     // ... (same as before)
  21. }
  22.  
  23. int main() {
  24.     int N, Q;
  25.     cin >> N >> Q;
  26.     for (int i = 1; i <= N; i++) {
  27.         cin >> P[i];
  28.         P_map[P[i]] = i;
  29.     }
  30.  
  31.     // Build the Segment Tree
  32.     build(1, 1, N);
  33.  
  34.     while (Q--) {
  35.         int type;
  36.         cin >> type;
  37.  
  38.         if (type == 0 || type == 1) {
  39.             int l, r, c;
  40.             cin >> l >> r >> c;
  41.  
  42.             if (type == 0) {
  43.                 // Update the range [l, r] in A
  44.                 for (int i = l; i <= r; i++) {
  45.                     update(1, 1, N, i, c);
  46.                 }
  47.             } else {
  48.                 // Update the range [P[l], P[r]] in A
  49.                 for (int i = l; i <= r; i++) {
  50.                     update(1, 1, N, P_map[i], c);
  51.                 }
  52.             }
  53.         } else if (type == 2 || type == 3) {
  54.             int l, r;
  55.             cin >> l >> r;
  56.  
  57.             if (type == 2) {
  58.                 // Query the sum of the range [l, r] in A
  59.                 cout << query(1, 1, N, l, r) << endl;
  60.             } else {
  61.                 // Query the sum of the range [P[l], P[r]] in A
  62.                 int sum = 0;
  63.                 for (int i = l; i <= r; i++) {
  64.                     sum += query(1, 1, N, P_map[i], P_map[i]);
  65.                 }
  66.                 cout << sum << endl;
  67.             }
  68.         }
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5300KB
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
0
0
https://ideone.com/e3MhmL
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!