记录编号	567276	评测结果	AAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.787 s
提交时间	2021-11-25 19:34:21	内存使用	18.25 MiB

//CDQ分治第一弹
//STO CDQ 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 5e5 + 5;
struct query {
	int op,id,x,y;//id:若当前操作为询问，则为询问的编号
	//op:1为修改，2为负查询，3为正查询
	//x,y:操作的点和要增加的量 
	query() {
		op = id = x = y = 0;
	}
	query(int op,int id,int x,int y):op(op),id(id),x(x),y(y){}
}Q[maxn],b[maxn];//b数组：辅助进行归并排序 
int n,m,cnt,tot,ans[maxn];
int read() {
	int s = 0,f = 1;
	char c = getchar();
	for(;!isdigit(c);c = getchar()) {
		if(c == '-')f = -1;
	}
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f;
}
void write(int x) {
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void print(int x) {
	write(x);
	putchar('\n');
	return ;
}//快读快写 
//个人对于CDQ分治的理解：
//主要是解决偏序问题，当然这些偏序不都是裸的类似逆序对这样的
//对于答案的修改可能更加繁琐一点
//但是核心思想都是用CDQ分治解决偏序
//1：solve(l,mid)，2：solve(mid+1,r)和3：(l,mid)对(mid+1,r)的影响这三块
//需要根据题目的要求自行决定顺序
//不恰当的栗子：DP
//DP时后半部分的计算直接由前半部分的影响决定
//这时就要1,3,2这样处理
//而对于本题，处理需要两个区间都有序，所以要先递归 ，即1,2,3 
void solve(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1 , r);
	//此处先递归是因为CDQ分治解决偏序类似归并排序
	//需要两个区间都是有序的才能进行进一步的处理
	int i = l,j = mid + 1,sum = 0;//Mergesort part
	//sum用来统计[l,mid]的修改对[mid + 1,r]的影响 
	for(int k = l;k <= r;++ k) {
		if(j > r||(i <= mid&&Q[i].x <= Q[j].x)) {
			//此时当前的i对于[j,r]区间都有影响
			//记录在sum里，当查找到一个i，使得i无法对于j产生影响
			//那么再统计前面所有的i对当前j的影响
			//写的不太明白，可以结合下面else部分中的代码理解 
			if(Q[i].op == 1) {
				sum += Q[i].y;
			}
			b[k] = Q[i ++];
		}
		else {
			if(Q[j].op == 2) {
				ans[Q[j].id] -= sum;
			}
			else ans[Q[j].id] += sum;
			//若当前询问是-操作，那么ans[Q[j].id]减去sum值（也就是前半部分的影响）
			//若为+操作，则刚好相反 
			b[k] = Q[j ++];
		}
	} 
	for(int k = l;k <= r;++ k) {
		Q[k] = b[k];//归并排序的合并部分
		//为了保证当前递归的上一层可以正常进行，需要让Q[l~r]有序
		//结合函数开头理解 
	}
	return ;
}
int main() {
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;++ i) {
		int x = read();
		Q[++ cnt] = query(1 , 0 , i , x);
	}
	m = read();
	for(int i = 1;i <= m;++ i) {
		char c[10];
		scanf("%s",c + 1);
		int x = read(),y = read();
		if(c[1] == 'A') {
			Q[++ cnt] = query(1 , 0 , x , y);
		}
		else {
			Q[++ cnt] = query(2 , ++ tot , x - 1 , 0);
			Q[++ cnt] = query(3 , tot , y , 0);
		}
	}
	solve(1 , cnt);
	for(int i = 1;i <= tot;++ i)print(ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}