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