记录编号	479318	评测结果	AAAAAAAAAA
题目名称	魔法传输	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	1.834 s
提交时间	2017-12-18 15:30:06	内存使用	3.75 MiB

#include<bits/stdc++.h>
#define ls ch[x][0]
#define rs ch[x][1]
#define ll long long
using namespace std;
const int inf=1e5+3;
const int mod=1e9+7;
ll a[inf],lazy1[inf],lazy2[inf];
int ch[inf][2],fa[inf],rt;
int n,m;
int get(int x){
	return ch[fa[x]][1]==x;
}
void pushdown(int x){
	if(ls)lazy1[ls]+=lazy1[x],lazy2[ls]+=lazy2[x],lazy1[ls]=(lazy1[ls]+mod)%mod,lazy2[ls]%=mod;
	if(rs)lazy1[rs]+=lazy1[x],lazy2[rs]+=lazy2[x],lazy1[rs]=(lazy1[rs]+mod)%mod,lazy2[rs]%=mod;
	a[x]+=lazy1[x]+1ll*lazy2[x]*x%mod;
	a[x]=(a[x]+mod)%mod;
	lazy1[x]=lazy2[x]=0;
}
void zig(int x){
	int old=fa[x],oldf=fa[old],p=get(x);
//	cout<<x<<" "<<old<<" "<<oldf<<endl;
	pushdown(old);
	pushdown(x);
	if(oldf)ch[oldf][get(old)]=x;
	fa[x]=oldf;
	fa[ch[old][p]=ch[x][p^1]]=old;
	fa[ch[x][p^1]=old]=x;
}
void splay(int x,int aim=0){
	for(int f;(f=fa[x])!=aim;zig(x)){
		if(fa[f]!=aim)zig(get(x)==get(f)?f:x);
	}
	if(!aim)rt=x;
}
void out(int x){
	if(ch[x][0])out(ch[x][0]);
	if(ch[x][1])out(ch[x][1]);
}
int build(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1;
	if(!rt)rt=mid;
	int Ls=build(l,mid-1);
	int Rs=build(mid+1,r);
	if(Ls)fa[ch[mid][0]=Ls]=mid;
	if(Rs)fa[ch[mid][1]=Rs]=mid;
	return mid;
}
int main()
{
	freopen("magics.in","r",stdin);
	freopen("magics.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	build(1,n+2);
	for(int i=1;i<=m;i++){
		char s[10];
		scanf("%s",s);
		if(s[0]=='C'){
			int l,r;
			scanf("%d%d",&l,&r);
			splay(l);
			splay(r+2,rt);
			int o=ch[r+2][0];
			lazy1[o]-=l;
			lazy2[o]++;
		}
		else {
			int x;
			scanf("%d",&x);
			x++;
			splay(x);
			printf("%lld\n",(a[x]+lazy1[x]+lazy2[x]*x%mod+mod)%mod);
		}
	}
	return 0;
}