记录编号	357232	评测结果	AAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.567 s
提交时间	2016-12-09 23:50:21	内存使用	20.53 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <list>
using namespace std;
#define MAXM 150001
#define MAXN 100001
struct que
{
	int id, tp, p, v, qid, sg;
	bool operator<(const que &oq)const
	{
		return p<oq.p;
	}
}qs[2*MAXM+MAXN+10], tmp[2*MAXM+MAXN+10];
typedef long long LL;
LL ans[MAXM];
LL s[MAXN];
int n;
void add(int x, LL v)
{
	for(; x <= n; x += x&-x)s[x] += v;
}
LL query(int x)
{
	LL r = 0;
	for(; x; x -= x&-x)r += s[x];
	return r;
}
void merge(int l, int r)
{
	if(l >= r)return;
	int m = (l+r)>>1;
    for(int i = l; i <= r; i++)
	    if(qs[i].id <= m && !qs[i].tp)add(qs[i].p, qs[i].v);
	    else if(qs[i].id > m && qs[i].tp)
	        ans[qs[i].qid] += query(qs[i].p)*qs[i].sg;
	for(int i = l; i <= r; i++)if(qs[i].id <= m && !qs[i].tp)
	    add(qs[i].p, -qs[i].v);
	int j = l, k = m+1, p = l;
	while(j <= m && k <= r)
		if(qs[j].id < qs[k].id)tmp[p++]=qs[j++];
		else tmp[p++]=qs[k++];
	while(j <= m)tmp[p++] = qs[j++];
	while(k <= r)tmp[p++] = qs[k++];
	for(int i = l; i <= r; i++)
        qs[i] = tmp[i];
    merge(l, m);
	merge(m+1, r);
}
int tot = 0;
void add_que(int p, int v, int tp, int qid, int sg = 1)
{
	++tot;
	qs[tot] = (que){tot, tp, p, v, qid, sg};
}
int main()
{
	freopen("shulie.in", "r", stdin);
	freopen("shulie.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1, j; i <= n; i++)
	{
		scanf("%d", &j);
		add_que(i, j, 0, 0);
	}
	int m;
	char bf[20];
	scanf("%d", &m);
	int asks = 0;
    while(m--)
	{
		int x, y;
		scanf("%s %d %d", bf, &x, &y);
		if(bf[0] == 'A')
		{
			add_que(x, y, 0, 0);
		}else if(bf[0] == 'S')
		{
		    ++asks;
		    add_que(x-1, 0, 1, asks, -1);
		    add_que(y, 0, 1, asks);			
		}
	}
	merge(1, tot);
	for(int i = 1; i <= asks; i++)
	    printf("%lld\n", ans[i]);
    return 0;
}
/*
4
1 4 2 3 
3
SUM 1 3 
ADD 2 50
SUM 2 3

7 56
*/