比赛 数列操作练习题 评测结果 AAAAAAAAAA
题目名称 数列操作d 最终得分 100
用户昵称 _Itachi 运行时间 2.705 s
代码语言 C++ 内存使用 32.33 MiB
提交时间 2017-03-18 19:05:46
显示代码纯文本
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. char cc;inline void R_int(register int &x){
  6. while(cc=getchar(),cc<'!');x=cc-48;
  7. while(cc=getchar(),cc>'!')x=x*10+cc-48;
  8. }
  9. char ss[11]="0123456789";
  10. char ccc[10];int cct=0;void R_out(register int x){
  11. if(!x)putchar('0');
  12. else{
  13. while(x)ccc[++cct]=x%10,x/=10;
  14. while(cct)putchar(ss[ccc[cct--]]);
  15. }
  16. putchar('\n');
  17. }
  18. #define LL long long
  19. const int maxn=300005<<1,INF=1000*1000*1000+7;
  20. int sum[maxn],mid[maxn];
  21. int ls[maxn],rs[maxn],s,t,qk,qb,cnt=0,RT;
  22. LL v[maxn],lzk[maxn],lzb[maxn],S[maxn],L[maxn];
  23. inline int Build(register int l,register int r){
  24. register int rt=++cnt;L[rt]=r-l+1;
  25. if(l==r){S[rt]=l;return rt;}
  26. mid[rt]=(l+r)>>1;
  27. ls[rt]=Build(l,mid[rt]),rs[rt]=Build(mid[rt]+1,r);
  28. S[rt]=S[ls[rt]]+S[rs[rt]];if(S[rt]>=INF)S[rt]-=INF;
  29. return rt;
  30. }
  31. inline void Add(register int rt,register int l,register int r){
  32. if(s<=l&&r<=t){
  33. v[rt]+=qk*S[rt]+qb*L[rt];if(v[rt]>=INF)v[rt]%=INF;
  34. lzk[rt]+=qk,lzb[rt]+=qb;
  35. if(lzk[rt]>=INF)lzk[rt]-=INF;
  36. if(lzb[rt]>=INF)lzb[rt]-=INF;
  37. return;
  38. }
  39. if(s<=mid[rt])Add(ls[rt],l,mid[rt]);
  40. if(t> mid[rt])Add(rs[rt],mid[rt]+1,r);
  41. v[rt]=v[ls[rt]]+v[rs[rt]]+lzk[rt]*S[rt]+lzb[rt]*L[rt];
  42. if(v[rt]>=INF)v[rt]%=INF;
  43. }
  44. inline LL Get(register int rt,register int l,register int r){
  45. if(s<=l&&r<=t)return v[rt];
  46. register int ll=max(l,s)-1,rr=min(t,r);
  47. LL res=lzk[rt]*(sum[rr]-sum[ll])+lzb[rt]*(rr-ll);
  48. if(res<0)res=res%INF+INF;
  49. if(s<=mid[rt])res+=Get(ls[rt],l,mid[rt]);
  50. if(t> mid[rt])res+=Get(rs[rt],mid[rt]+1,r);
  51. if(res>=INF)res%=INF;return res;
  52. }
  53. int main(){
  54. freopen("segment.in","r",stdin);freopen("segment.out","w",stdout);
  55. register int n,m,o,i;R_int(n),R_int(m);
  56. RT=Build(1,n);
  57. for(i=1;i<=n;i++)sum[i]=(sum[i-1]+i)%INF;
  58. while(m--){
  59. R_int(o),R_int(s),R_int(t);
  60. if(!o)R_out(Get(RT,1,n)%INF);
  61. else R_int(qk),qb=INF-(s*1ll*qk)%INF,Add(RT,1,n);
  62. }
  63. fclose(stdin);fclose(stdout);return 0;
  64. }