- #include <bits/stdc++.h>
- using namespace std;
- const int MAX = 112345;
- struct Node {
- int minn;
- int lazy;
- int sum;
- } tree[MAX * 4];
- int data[MAX];
- #define lson (o<<1)
- #define rson (o<<1|1)
- #define MID int m = (l + r) / 2
- void push_down(int o) {
- if (tree[o].lazy) {
- int &lazy = tree[o].lazy;
- tree[lson].minn -= lazy;
- tree[rson].minn -= lazy;
- tree[lson].lazy += lazy;
- tree[rson].lazy += lazy;
- lazy = 0;
- }
- }
- void build(int o, int l, int r) {
- tree[o].lazy = 0;
- if (l == r) {
- tree[o].minn = data[l];
- tree[o].sum = 0;
- return;
- }
- MID;
- build(lson, l, m);
- build(rson, m + 1, r);
- tree[o].minn = min(tree[lson].minn, tree[rson].minn);
- tree[o].sum = tree[lson].sum + tree[rson].sum;
- }
- void update(int o, int l, int r, int ql, int qr) {
- if (qr < l || r < ql) return;
- if (ql <= l && r <= qr) {
- tree[o].lazy += 1;
- tree[o].minn -= 1;
- return;
- }
- push_down(o);
- MID;
- update(lson, l, m, ql, qr);
- update(rson, m + 1, r, ql, qr);
- tree[o].minn = min(tree[lson].minn, tree[rson].minn);
- tree[o].sum = tree[lson].sum + tree[rson].sum;
- }
- int ans = 0;
- void dfs(int o, int l, int r) {
- if (l == r) {
- tree[o].minn = data[l];
- tree[o].sum++;
- return;
- }
- push_down(o);
- MID;
- if (tree[lson].minn == 0) dfs(lson, l, m);
- if (tree[rson].minn == 0) dfs(rson, m + 1, r);
- tree[o].minn = min(tree[lson].minn, tree[rson].minn);
- tree[o].sum = tree[lson].sum + tree[rson].sum;
- }
- int query(int o, int l, int r, int ql, int qr) {
- if (qr < l || r < ql) return 0;
- if (ql <= l && r <= qr) {
- return tree[o].sum;
- }
- push_down(o);
- MID;
- return query(lson, l, m, ql, qr) + query(rson, m + 1, r, ql, qr);
- }
- int main() {
- int n, m;
- while(~scanf("%d %d", &n, &m)){
- for (int i = 1; i <= n; i++) scanf("%d", data + i);
- build(1, 1, n);
- while (m--) {
- char op[10];
- int l, r;
- scanf("%s %d %d", op, &l, &r);
- if (op[0] == 'a') {
- update(1, 1, n, l, r);
- dfs(1, 1, n);
- } else {
- printf("%d\n", query(1, 1, n, l, r));
- }
- }
- }
- return 0;
- }