如题

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ls t[u << 1]
#define rs t[u << 1 | 1]
const int maxn = 1e5 + 5;
const int mod = 1e9 + 9;

ll p[maxn];

struct edge {
    int l, r;
    ll w, add, mn;
};

struct tree {
    vector<edge> t;

    tree(int n) :
            t(n << 3) {}

    void push_up(int u) {
        t[u].w = (ls.w + rs.w) % mod;
        t[u].mn = min(ls.mn, rs.mn);
    }

    void build(int u, int l, int r) {
        t[u].l = l;
        t[u].r = r;
        if (l == r) {
            t[u].w = p[l];
            t[u].mn = p[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    void push_down(int u) {
        if (t[u].add) {
            ls.w = (ls.w + t[u].add * (ls.r - ls.l + 1) % mod) % mod;
            ls.add = (ls.add + t[u].add) % mod;
            ls.mn = (ls.mn + t[u].add) % mod;
            rs.w = (rs.w + t[u].add * (rs.r - rs.l + 1) % mod) % mod;
            rs.add = (rs.add + t[u].add) % mod;
            rs.mn = (rs.mn + t[u].add) % mod;
        }
        t[u].add = 0;
    }

    void modify(int u, int l, int r, ll v) {
        if (t[u].l >= l && t[u].r <= r) {
            t[u].w = (t[u].w + v * (t[u].r - t[u].l + 1) % mod) % mod;
            t[u].mn = (t[u].mn + v) % mod;
            t[u].add += v;
        } else {
            push_down(u);
            int mid = (t[u].l + t[u].r) >> 1;
            if (mid >= l) {
                modify(u << 1, l, mid, v);
            }
            if (mid < r) {
                modify(u << 1 | 1, mid + 1, r, v);
            }
            push_up(u);
        }
    }

    void change(int u, int x, ll v) {
        if (t[u].l == x && t[u].r == x) {
            t[u].w = v;
            t[u].mn = v;
        } else {
            push_down(u);
            int mid = (t[u].l + t[u].r) >> 1;
            if (mid >= x) {
                change(u << 1, x, v);
            } else {
                change(u << 1 | 1, x, v);
            }
            push_up(u);
        }
    }

    ll query(int u, int x) {
        if (t[u].l == x && t[u].r == x) {
            return t[u].w;
        } else {
            push_down(u);
            int mid = (t[u].l + t[u].r) >> 1;
            if (mid >= x) {
                return query(u << 1, x);
            } else {
                return query(u << 1 | 1, x);
            }
        }
    }

    int find_id(int u) {
        if (t[u].l == t[u].r) {
            return t[u].l;
        } else {
            push_down(u);
            if (t[u].mn == ls.mn) {
                return find_id(u << 1);
            } else {
                return find_id(u << 1 | 1);
            }
        }
    }
};
bool vis[maxn];

void solve() {
    int n, q;
    cin >> n >> q;
    tree t2(n);
    t2.build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    tree t1(n);
    t1.build(1, 1, n);

    ll ans = 0;
    while (q--) {
        char opt;
        cin >> opt;
        if (opt == 'A') {
            int l, r;
            ll a;
            cin >> l >> r >> a;
            t1.modify(1, l, r, -a);
            t2.modify(1, l, r, 2 * a);
            while (t1.t[1].mn <= 0) {
                int idx = t1.find_id(1);
                ll val = t1.query(1, idx);
                vis[idx] = true;
                t2.change(1, idx, p[idx] - val);
                t1.change(1, idx, mod);
            }
        } else {
            int x;
            cin >> x;
            if (vis[x]) {
                ans = (ans + t2.query(1, x)) % mod;
            } else {
                ans = (ans + p[x] - t1.query(1, x)) % mod;
            }
        }
    }
    cout << ans;
}


int main() {
    solve();
}