Advertisement
Josif_tepe

Untitled

Dec 30th, 2023
864
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4.  
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. typedef long long ll;
  8. int a[maxn], n;
  9. ll segment_tree[3 * maxn];
  10. ll lazy[3 * maxn];
  11. void build(int L, int R, int node) {
  12.     if(L == R) {
  13.         segment_tree[node] = a[L];
  14.     }
  15.     else {
  16.         int mid = (L + R) / 2;
  17.         build(L, mid, 2 * node);
  18.         build(mid + 1, R, 2 * node + 1);
  19.         segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  20.     }
  21. }
  22. void push_lazy(int L, int R, int node) {
  23.     if(lazy[node] == 0) {
  24.         return;
  25.     }
  26.     segment_tree[node] += (R - L + 1) * lazy[node];
  27.     if(L != R) {
  28.         lazy[2 * node] += lazy[node];
  29.         lazy[2 * node + 1] += lazy[node];
  30.     }
  31.     lazy[node] = 0;
  32. }
  33. void update(int L, int R, int node, int i, int j, int value) {
  34.     push_lazy(L, R, node);
  35.     if(L > R or i > R or L > j) return;
  36.    
  37.     if(i <= L and R <= j) {
  38.         lazy[node] += value;
  39.         push_lazy(L, R, node);
  40.         return;
  41.     }
  42.     int mid = (L + R) / 2;
  43.     update(L, mid, 2 * node, i, j, value);
  44.     update(mid + 1, R, 2 * node + 1, i, j, value);
  45.     segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
  46. }
  47. ll query(int L, int R, int node, int pos) {
  48.     // pos L pos R pos
  49.     if(L > R or L > pos or pos > R) {
  50.         return 0;
  51.     }
  52.     push_lazy(L, R, node);
  53.     if(L == R) {
  54.         return segment_tree[node];
  55.     }
  56.     int mid = (L + R) / 2;
  57.     if(pos <= mid) {
  58.         return query(L, mid, 2 * node, pos);
  59.     }
  60.     return query(mid + 1, R, 2 * node + 1, pos);
  61. }
  62. int first_left_binary_search(int L, int R, int h) {
  63.     int res = n;
  64.     while(L <= R) {
  65.         int mid = (L + R) / 2;
  66.         if(query(0, n - 1, 1, mid) >= h) {
  67.             res = mid;
  68.             R = mid - 1;
  69.         }
  70.         else {
  71.             L = mid + 1;
  72.         }
  73.     }
  74.     return res;
  75. }
  76. int new_left_binary_search(int L, int R, int try_right) {
  77.     int res = n;
  78.     while(L <= R) {
  79.         int mid = (L + R) / 2;
  80.         if(query(0, n - 1, 1, mid) >= query(0, n - 1, 1, try_right)) {
  81.             res = mid;
  82.             R = mid - 1;
  83.         }
  84.         else {
  85.             L = mid + 1;
  86.         }
  87.     }
  88.     return res;
  89. }
  90. int new_right_binary_search(int L, int R, int try_right) {
  91.     int res = n;
  92.     while(L <= R) {
  93.         int mid = (L + R) / 2;
  94.         if(query(0, n - 1, 1, mid) > query(0, n - 1, 1, try_right)) {
  95.             res = mid;
  96.             R = mid - 1;
  97.         }
  98.         else {
  99.             L = mid + 1;
  100.         }
  101.     }
  102.     return res;
  103. }
  104. int min_binary_search(int L, int R, int min) {
  105.     int res = n;
  106.     while(L <= R) {
  107.         int mid = (L + R) / 2;
  108.         if(query(0, n - 1, 1, mid) >= mid) {
  109.             res = mid;
  110.             R = mid - 1;
  111.         }
  112.         else {
  113.             L = mid + 1;
  114.         }
  115.     }
  116.     return res;
  117. }
  118. int max_binary_search(int L, int R, int max) {
  119.     int res = n;
  120.     while(L <= R) {
  121.         int mid = (L + R) / 2;
  122.         if(query(0, n - 1, 1, mid) > max) {
  123.             res = mid;
  124.             R = mid - 1;
  125.         }
  126.         else {
  127.             L = mid + 1;
  128.         }
  129.     }
  130.     return res;
  131. }
  132. int main()
  133. {
  134.     memset(lazy, 0, sizeof lazy);
  135.     int q;
  136.     cin >> n >> q;
  137.     for(int i = 0; i < n; i++) {
  138.         cin >> a[i];
  139.     }
  140.     build(0, n - 1, 1);
  141.     for(int i = 0; i < q; i++) {
  142.         char type;
  143.         cin >> type;
  144.         if(type == 'F') {
  145.             int c, h;
  146.             cin >> c >> h;
  147.             int first_left = first_left_binary_search(0, n - 1, h);
  148.             int try_right = first_left + c - 1;
  149.             if(try_right >= n - 1) {
  150.                 update(0, n - 1, 1, first_left, try_right, 1);
  151.                 continue;
  152.             }
  153.             int new_left = new_left_binary_search(first_left, n - 1, try_right);
  154.             int new_right = new_right_binary_search(new_left, n - 1, try_right) - 1;
  155.             update(0, n - 1, 1, first_left, new_left - 1, 1);
  156.             update(0, n - 1, 1, new_right - c + new_left - first_left + 1, new_right, 1);
  157.            
  158. //            for(int i = 0; i < n; i++) {
  159. //                cout << query(0, n - 1, 1, i) << " ";
  160. //            }
  161. //            cout << endl;
  162.         }
  163.         else {
  164.             int minimum, maximum;
  165.             cin >> minimum >> maximum;
  166.             if(query(0, n - 1, 1, n - 1) < minimum) {
  167.                 cout << "0\n";
  168.                 continue;
  169.             }
  170.             int L = min_binary_search(0, n - 1,  minimum);
  171.             int R = max_binary_search(0, n - 1, maximum);
  172.             cout << R - L << "\n";
  173.         }
  174.     }
  175.     return 0;
  176. }
  177.  
  178.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement