记录编号	452237	评测结果	AAAAAAAAAA
题目名称	魔法传输	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	1.769 s
提交时间	2017-09-19 08:03:06	内存使用	19.39 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#define mid (l+r>>1)
#define ls (o<<1)
#define rs ((o<<1)+1)
#define av 0.5 

using namespace std;

const int MOD=1e9+7;
long long n,m,dep[600010],ha[100010],ans,lazc[600010];
double lazy[600010],num[600010];
void buildt(int l,int r,int o)
{
	if(l==r){
		return;
	}
	buildt(l,mid,ls);
	buildt(mid+1,r,rs);
	dep[o]=dep[ls]+1;
	return;
}

void pushdown(int l,int r,int o)
{
	if(dep[o]==0||lazy[o]==0) return;
	lazc[ls]+=lazc[o];
	num[ls]+=lazy[o]-(double)lazc[o]*pow(2,dep[o]-1)*av;
	lazy[ls]+=lazy[o]-(double)lazc[o]*pow(2,dep[o]-1)*av;
	lazc[rs]+=lazc[o];
	num[rs]+=lazy[o]+(double)lazc[o]*pow(2,dep[o]-1)*av;
	lazy[rs]+=lazy[o]+(double)lazc[o]*pow(2,dep[o]-1)*av;
	lazy[o]=0.00;
	lazc[o]=0;
}

void change(int l,int r,int o,int ll,int rr)
{
	if(l>=ll&&r<=rr){
		if(l==r){
			num[o]+=(double)(l-ll+1);
		}
		else{
			num[o]+=(double)(l-ll+r-ll+2)/2.0;
			lazy[o]+=(double)(l-ll+r-ll+2)/2.0;
			lazc[o]++;
		}
		return;
	}
	pushdown(l,r,o);
	if(mid>=ll) change(l,mid,ls,ll,rr);
	if(mid<rr) change(mid+1,r,rs,ll,rr);
	return;
}

void query(int l,int r,int o,int p)
{	
	if(l==r){
		if(l==p){
			ans=(long long)num[o];
		}
		return;
	}
	pushdown(l,r,o);
	if(mid>=p) query(l,mid,ls,p);
	else query(mid+1,r,rs,p);
	return;
}

int main()
{
	freopen("magics.in","r",stdin);
	freopen("magics.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	long long temp=1;
	for(int i=1;i<=n;i++){
		if(i>temp){
			temp*=2;
		}
		ha[i]=temp;
	}
	buildt(1,ha[n],1);
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		if(c=='C'){
			int a,b;
			scanf("%d%d",&a,&b);
			change(1,ha[n],1,a,b);
		}
		else{
			int a;
			scanf("%d",&a);
			query(1,ha[n],1,a);
			printf("%lld\n",ans%MOD);
		}
	}//system("pause");
	return 0;
}