rt.

提交：https://www.luogu.com.cn/record/37466387

#include <cstdio>
#include <cctype>
using namespace std;

typedef long long ll;
constexpr int max_n = 131072;
const ll mod = 1e9 + 9;

struct node
{
	int mn, mn_pos, tag;
};

node tr[(max_n<<1)+1];
int orig[max_n], n;
ll bt[max_n];

inline int ls(int id) { return id << 1; }
inline int rs(int id) { return (id << 1) | 1; }
inline int lowbit(int x) { return x & -x; }

inline int read()
{
	int ch = getchar(), t = 1, n = 0;
	while (isspace(ch)) { ch = getchar(); }
	if (ch == '-') { t = -1, ch = getchar(); }
	while (isdigit(ch)) { n = n * 10 + ch - '0', ch = getchar(); }
	return n * t;
}

inline char getlc()
{
	char ch = getchar();
	while (isspace(ch))
		ch = getchar();
	return ch;
}

void add(int p, int v)
{
	while (p <= n)
	{
		bt[p] += v;
		p += lowbit(p);
	}
}

ll get(int p)
{
	ll res = 0;

	while (p > 0)
	{
		res += bt[p];
		p -= lowbit(p);
	}

	return res;
}

void pushdown(int id)
{
	if (tr[id].mn > 0)
		tr[id].mn -= tr[id].tag;
	
	tr[ls(id)].tag += tr[id].tag, tr[rs(id)].tag += tr[id].tag;
	tr[id].tag = 0;
}

void update(int id)
{
	if (tr[ls(id)].mn <= 0)
		tr[id].mn = tr[rs(id)].mn, tr[id].mn_pos = tr[rs(id)].mn_pos;
	else
	{
		if (tr[rs(id)].mn <= 0)
			tr[id].mn = tr[ls(id)].mn, tr[id].mn_pos = tr[ls(id)].mn_pos;
		else
		{
			if (tr[ls(id)].mn < tr[rs(id)].mn)
				tr[id].mn = tr[ls(id)].mn, tr[id].mn_pos = tr[ls(id)].mn_pos;
			else
				tr[id].mn = tr[rs(id)].mn, tr[id].mn_pos = tr[rs(id)].mn_pos;
		}
	}
}

void build(int l, int r, int id)
{
	tr[id].tag = 0;

	if (l == r)
	{
		tr[id].mn = orig[l-1], tr[id].mn_pos = l;
	//	printf("%d ", tr[id].mn);
		return;
	}

	int mid = (l + r) >> 1;

	build(l, mid, ls(id));
	build(mid + 1, r, rs(id));
	update(id);
}

void modify(int L, int R, int l, int r, int id, int val)
{
	if (L <= l && r <= R)
	{
		tr[id].tag += val;
	//	printf("-> %d %d %d %d\n", l, r, tr[id].mn, tr[id].tag);

		return;
	}

	pushdown(id);

	int mid = (l + r) >> 1;

//	printf("%d %d %d\n", l, r, id);

	if (L <= mid && l <= R)
		modify(L, R, l, mid, ls(id), val);
	if (L <= r && mid < R)
		modify(L, R, mid + 1, r, rs(id), val);
	
	update(id);
}

int query(int l, int r, int pos, int id)
{
	if (l == pos && pos == r)
	{
	//	printf("-< %d %d %d\n", pos, tr[id].mn, tr[id].tag);
		
		if (tr[id].mn > 0)
			tr[id].mn -= tr[id].tag;
		tr[id].tag = 0;
		
	//	printf("-< %d %d %d\n", pos, tr[id].mn, tr[id].tag);

		return tr[id].mn;
	}

	int mid = (l + r) >> 1, ans;
	pushdown(id);

	if (l <= pos && pos <= mid)
		ans = query(l, mid, pos, ls(id));
	else
		ans = query(mid + 1, r, pos, rs(id));
	
	update(id);
	return ans;
}

int main()
{
	int q, ta, tb, tc;
	ll tmp, ans = 0;
	char opt;

	n = read(), q = read();
	for (int i = 0; i < n; i++)
		orig[i] = read();
	
	build(1, n, 1);

	for (int i = 0; i < q; i++)
	{
		opt = getlc();

		if (opt == 'A')
		{
			ta = read(), tb = read(), tc = read();
			
			add(ta, tc);
			add(tb+1, -tc);
			modify(ta, tb, 1, n, 1, tc);
		}
		else
		{
		//	printf("%c %d\n", opt, opt);

			ta = read();

			ll tmp = get(ta);
			ans = (ans + 2 * tmp - (orig[ta-1] - query(1, n, ta, 1))) % mod;

		//	printf("--- %d %d %d\n", get(ta), orig[ta-1], query(1, n, ta, 1));
		}
	}

	printf("%lld\n", ans);

	return 0;
}