记录编号	323517	评测结果	AAAAAAAAAA
题目名称	魔法传输	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.956 s
提交时间	2016-10-16 19:05:22	内存使用	3.75 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxn 100100
using namespace std;
int seg[4*maxn],lazy[4*maxn],mark[maxn];
int n,m;
void push_down(int l,int r,int o){
	int k=lazy[o];
	lazy[o]=0;
	if(l==r)
	return;
	int mid=(l+r)/2;
	lazy[o<<1]+=k;
	lazy[o<<1|1]+=k;
	seg[o<<1]+=k*(mid-l+1);
	seg[o<<1|1]+=k*(r-mid);
	return ;
} 
void change(int x,int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		lazy[o]+=x;
		seg[o]+=x*(r-l+1);
		return ;
	}
	if(lazy[o]!=0){
		push_down(l,r,o);
	}
	int mid=(l+r)/2;
	if(ll<=mid){
		change(x,l,mid,o<<1,ll,rr);
	}
	if(rr>mid){
		change(x,mid+1,r,o<<1|1,ll,rr);
	}
	seg[o]=seg[o<<1|1]+seg[o<<1];
	return;
}
int query(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr){
		return seg[o];
	}
	if(lazy[o]!=0){
		push_down(l,r,o);
	}
	int mid=(l+r)/2;
	int anss=0;
	if(ll<=mid){
		anss+=query(l,mid,o<<1,ll,rr);
	}
	if(rr>mid){
		anss+=query(mid+1,r,o<<1|1,ll,rr);
	}
	seg[o]=seg[o<<1]+seg[o<<1|1];
	return anss;
}
void get_input(){
	cin>>n>>m;
	//build(0,n-1,1);
	for(int i=0;i<m;i++){
		int a;
		char t;
		cin>>t>>a;
		if(t=='Q'){ 
			cout<<query(0,n-1,1,0,a-1)<<endl;
		}
		else{
			int temp;
			cin>>temp;
			change(1,0,n-1,1,a-1,temp-1);
			if(temp!=n)
			change(-(temp-a+1),0,n-1,1,temp,temp);
		}
	}
}
int main(){
	freopen("magics.in","r",stdin);
	freopen("magics.out","w",stdout);
	get_input();
}