比赛 数列操作练习题 评测结果 AAAAAAAAAA
题目名称 数列操作d 最终得分 100
用户昵称 _Itachi 运行时间 2.705 s
代码语言 C++ 内存使用 32.33 MiB
提交时间 2017-03-18 19:05:46
显示代码纯文本
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char cc;inline void R_int(register int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
char ss[11]="0123456789";
char ccc[10];int cct=0;void R_out(register int x){
	if(!x)putchar('0');
	else{
		while(x)ccc[++cct]=x%10,x/=10;
		while(cct)putchar(ss[ccc[cct--]]);
	}
	putchar('\n');
}
#define LL long long
const int maxn=300005<<1,INF=1000*1000*1000+7;
int sum[maxn],mid[maxn];
int ls[maxn],rs[maxn],s,t,qk,qb,cnt=0,RT;
LL v[maxn],lzk[maxn],lzb[maxn],S[maxn],L[maxn];
inline int Build(register int l,register int r){
	register int rt=++cnt;L[rt]=r-l+1;
	if(l==r){S[rt]=l;return rt;}
	mid[rt]=(l+r)>>1;
	ls[rt]=Build(l,mid[rt]),rs[rt]=Build(mid[rt]+1,r);
	S[rt]=S[ls[rt]]+S[rs[rt]];if(S[rt]>=INF)S[rt]-=INF;
	return rt;
}
inline void Add(register int rt,register int l,register int r){
	if(s<=l&&r<=t){
		v[rt]+=qk*S[rt]+qb*L[rt];if(v[rt]>=INF)v[rt]%=INF;
		lzk[rt]+=qk,lzb[rt]+=qb;
		if(lzk[rt]>=INF)lzk[rt]-=INF;
		if(lzb[rt]>=INF)lzb[rt]-=INF;
		return;
	}
	if(s<=mid[rt])Add(ls[rt],l,mid[rt]);
	if(t> mid[rt])Add(rs[rt],mid[rt]+1,r);
	v[rt]=v[ls[rt]]+v[rs[rt]]+lzk[rt]*S[rt]+lzb[rt]*L[rt];
	if(v[rt]>=INF)v[rt]%=INF;
}
inline LL Get(register int rt,register int l,register int r){
	if(s<=l&&r<=t)return v[rt];
	register int ll=max(l,s)-1,rr=min(t,r);
	LL res=lzk[rt]*(sum[rr]-sum[ll])+lzb[rt]*(rr-ll);
	if(res<0)res=res%INF+INF;
	if(s<=mid[rt])res+=Get(ls[rt],l,mid[rt]);
	if(t> mid[rt])res+=Get(rs[rt],mid[rt]+1,r);
	if(res>=INF)res%=INF;return res;
}
int main(){
	freopen("segment.in","r",stdin);freopen("segment.out","w",stdout);
	register int n,m,o,i;R_int(n),R_int(m);
	RT=Build(1,n);
	for(i=1;i<=n;i++)sum[i]=(sum[i-1]+i)%INF;	
	while(m--){
		R_int(o),R_int(s),R_int(t);
		if(!o)R_out(Get(RT,1,n)%INF);
		else R_int(qk),qb=INF-(s*1ll*qk)%INF,Add(RT,1,n);
	}
	fclose(stdin);fclose(stdout);return 0;
}