Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- using namespace std;
- const int maxn = 1e5 + 10;
- typedef long long ll;
- int a[maxn], n;
- ll segment_tree[3 * maxn];
- ll lazy[3 * maxn];
- void build(int L, int R, int node) {
- if(L == R) {
- segment_tree[node] = a[L];
- }
- else {
- int mid = (L + R) / 2;
- build(L, mid, 2 * node);
- build(mid + 1, R, 2 * node + 1);
- segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
- }
- }
- void push_lazy(int L, int R, int node) {
- if(lazy[node] == 0) {
- return;
- }
- segment_tree[node] += (R - L + 1) * lazy[node];
- if(L != R) {
- lazy[2 * node] += lazy[node];
- lazy[2 * node + 1] += lazy[node];
- }
- lazy[node] = 0;
- }
- void update(int L, int R, int node, int i, int j, int value) {
- push_lazy(L, R, node);
- if(L > R or i > R or L > j) return;
- if(i <= L and R <= j) {
- lazy[node] += value;
- push_lazy(L, R, node);
- return;
- }
- int mid = (L + R) / 2;
- update(L, mid, 2 * node, i, j, value);
- update(mid + 1, R, 2 * node + 1, i, j, value);
- segment_tree[node] = segment_tree[2 * node] + segment_tree[2 * node + 1];
- }
- ll query(int L, int R, int node, int pos) {
- // pos L pos R pos
- if(L > R or L > pos or pos > R) {
- return 0;
- }
- push_lazy(L, R, node);
- if(L == R) {
- return segment_tree[node];
- }
- int mid = (L + R) / 2;
- if(pos <= mid) {
- return query(L, mid, 2 * node, pos);
- }
- return query(mid + 1, R, 2 * node + 1, pos);
- }
- int first_left_binary_search(int L, int R, int h) {
- int res = n;
- while(L <= R) {
- int mid = (L + R) / 2;
- if(query(0, n - 1, 1, mid) >= h) {
- res = mid;
- R = mid - 1;
- }
- else {
- L = mid + 1;
- }
- }
- return res;
- }
- int new_left_binary_search(int L, int R, int try_right) {
- int res = n;
- while(L <= R) {
- int mid = (L + R) / 2;
- if(query(0, n - 1, 1, mid) >= query(0, n - 1, 1, try_right)) {
- res = mid;
- R = mid - 1;
- }
- else {
- L = mid + 1;
- }
- }
- return res;
- }
- int new_right_binary_search(int L, int R, int try_right) {
- int res = n;
- while(L <= R) {
- int mid = (L + R) / 2;
- if(query(0, n - 1, 1, mid) > query(0, n - 1, 1, try_right)) {
- res = mid;
- R = mid - 1;
- }
- else {
- L = mid + 1;
- }
- }
- return res;
- }
- int min_binary_search(int L, int R, int min) {
- int res = n;
- while(L <= R) {
- int mid = (L + R) / 2;
- if(query(0, n - 1, 1, mid) >= mid) {
- res = mid;
- R = mid - 1;
- }
- else {
- L = mid + 1;
- }
- }
- return res;
- }
- int max_binary_search(int L, int R, int max) {
- int res = n;
- while(L <= R) {
- int mid = (L + R) / 2;
- if(query(0, n - 1, 1, mid) > max) {
- res = mid;
- R = mid - 1;
- }
- else {
- L = mid + 1;
- }
- }
- return res;
- }
- int main()
- {
- memset(lazy, 0, sizeof lazy);
- int q;
- cin >> n >> q;
- for(int i = 0; i < n; i++) {
- cin >> a[i];
- }
- build(0, n - 1, 1);
- for(int i = 0; i < q; i++) {
- char type;
- cin >> type;
- if(type == 'F') {
- int c, h;
- cin >> c >> h;
- int first_left = first_left_binary_search(0, n - 1, h);
- int try_right = first_left + c - 1;
- if(try_right >= n - 1) {
- update(0, n - 1, 1, first_left, try_right, 1);
- continue;
- }
- int new_left = new_left_binary_search(first_left, n - 1, try_right);
- int new_right = new_right_binary_search(new_left, n - 1, try_right) - 1;
- update(0, n - 1, 1, first_left, new_left - 1, 1);
- update(0, n - 1, 1, new_right - c + new_left - first_left + 1, new_right, 1);
- // for(int i = 0; i < n; i++) {
- // cout << query(0, n - 1, 1, i) << " ";
- // }
- // cout << endl;
- }
- else {
- int minimum, maximum;
- cin >> minimum >> maximum;
- if(query(0, n - 1, 1, n - 1) < minimum) {
- cout << "0\n";
- continue;
- }
- int L = min_binary_search(0, n - 1, minimum);
- int R = max_binary_search(0, n - 1, maximum);
- cout << R - L << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement