比赛 20160421x 评测结果 WWWWWEEEEW
题目名称 魔法传输 最终得分 0
用户昵称 mikumikumi 运行时间 0.402 s
代码语言 C++ 内存使用 2.60 MiB
提交时间 2016-04-21 16:28:32
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=100010;
typedef long long LL;
const LL MOD=1000000007;
int N,M;
class miku
{
public:
	int l,r;
	LL sum;
	LL lazy;
}tr[SIZEN];
void built(int root,int l,int r)
{
	tr[root].l=l;tr[root].r=r;
	tr[root].sum=0;
	if(l<r)
	{
		int mid=(l+r)/2;
		built(root<<1,l,mid);
		built(root<<1|1,mid+1,r);
	}
}
void read()
{
	scanf("%d%d",&N,&M);
	built(1,1,N);
}
void update(int root,int t)
{
	tr[root].sum+=t*(tr[root].r-tr[root].l+1);
	tr[root].sum%=MOD;
	tr[root].lazy+=t;
}
void pushdown(int root)
{
	update(root<<1,tr[root].lazy);
	update(root<<1|1,tr[root].lazy);
	tr[root].lazy=0;
}
void add(int root,int l,int r,int t)
{
	if(l>tr[root].r||r<tr[root].l) return;
	if(l<=tr[root].l&&tr[root].r<=r) 
	{
		update(root,t);
		return;
	}
	pushdown(root);
	add(root<<1,l,r,t);add(root<<1|1,l,r,t);
	tr[root].sum=tr[root<<1].sum+tr[root<<1|1].sum;
	tr[root].sum%=MOD;
}
LL query(int root,int l,int r)
{
	LL re=0;
	if(l>tr[root].r||r<tr[root].l) return re;
	//cout<<tr[root].l<<" "<<tr[root].r<<" "<<tr[root].sum<<endl;
	if(l<=tr[root].l&&tr[root].r<=r) return tr[root].sum;
	pushdown(root);
	re=query(root<<1,l,r)+query(root<<1|1,l,r);
	re%=MOD;
	return re;
}
void work()
{
	char cmd[2];
	int l,r;
	for(int i=1;i<=M;i++)
	{
		scanf("%s",cmd);
		if(cmd[0]=='C')
		{
			scanf("%d%d",&l,&r);
			add(1,l,r,1);
			//cout<<tr[1].sum<<endl;
		}
		else
		{
			scanf("%d",&r);
			LL ans=query(1,1,r);
			printf("%lld\n",ans);
		}
	}
}
int main()
{
	freopen("magics.in","r",stdin);
	freopen("magics.out","w",stdout);
	read();
	work();
	return 0;
}