Description：

由 $n$ 个防御体，刚开始有护甲，每次会有一轮伤害，如果伤害的和大于护甲护甲就会爆，如果没有护甲了伤害会翻倍，支持查询防御体收到了多少伤害。

$1\leqslant n\leqslant 10^5$

Solution：

发现护甲只会爆一次，在线段树上维护一个这段区间中护甲最小值是多少，如果最小值小于伤害，那么说明这个区间中有一个护甲会爆，那么就不停递归进入会爆的那棵子树并暴力标记，同时记录截止到当前为止这个护甲承受了多少伤害，在讯问时如果这个位置护甲没爆，那就是受到的总伤害，否则就是收到的总伤害乘二减去护甲承受的伤害，因为每个护甲只会爆一次所以复杂度 $O(n\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000009

inline char getc()

{

	register char c = getchar();

	while(c != 'A' && c != 'Q')c = getchar();

	return c;

}

int n,q;

#define MAXN 100010

int p[MAXN];

struct node

{

	int lc,rc;

	int minv,hurt;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].minv = p[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int hurt[MAXN],defence[MAXN];

#define INF 0x3f3f3f3f

void pushdown(int rt)

{

	t[t[rt].lc].minv -= t[rt].hurt;t[t[rt].lc].hurt += t[rt].hurt;

	t[t[rt].rc].minv -= t[rt].hurt;t[t[rt].rc].hurt += t[rt].hurt;

	t[rt].hurt = 0;

	return;

}

bool destroyed[MAXN];

void change(int rt,int k,int l,int r)

{

	if(l == r)

	{

		destroyed[l] = true;

		defence[l] = t[rt].hurt;

		t[rt].minv = INF;

		return;

	}

	pushdown(rt);

	if(t[t[rt].lc].minv <= 0)change(t[rt].lc,k,l,mid);

	if(t[t[rt].rc].minv <= 0)change(t[rt].rc,k,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].minv -= k;

		t[rt].hurt += k;

		if(t[rt].minv <= 0)change(rt,k,l,r);

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int query(int rt,int p,int l,int r)

{

	if(l == r)

	{

		if(destroyed[l])return t[rt].hurt * 2 - defence[l];

		else return t[rt].hurt;

	}

	pushdown(rt);

	if(p <= mid)return query(t[rt].lc,p,l,mid);

	else return query(t[rt].rc,p,mid + 1,r);

}

int main()

{

	scanf("%d%d",&n,&q);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	build(root,1,n);

	char opt;

	int l,r,k;

	int ans = 0;

	for(int i = 1;i <= q;++i)

	{

		opt = getc();

		if(opt == 'A')

		{

			scanf("%d%d%d",&l,&r,&k);

			add(root,l,r,k,1,n);

		}

		else

		{

			scanf("%d",&k);

			ans = (ans + query(root,k,1,n)) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}