比赛 |
数列操作练习题 |
评测结果 |
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;
}