fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5, MOD=1e9+7;
  4. long long n,q,a[MaxN];
  5. struct Segtree_lazy
  6. {
  7.     vector<long long> st,lazy_x,lazy_y;
  8.     void init(long long n)
  9.     {
  10.         if(n==0)
  11.         {
  12.             return;
  13.         }
  14.         st.assign(4*n+1,0);
  15.         lazy_x.assign(4*n+1,0);
  16.         lazy_y.assign(4*n+1,0);
  17.     }
  18.     void build(long long id, long long l, long long r)
  19.     {
  20.         if(l==r)
  21.         {
  22.             st[id]=a[l]%MOD;
  23.             return;
  24.         }
  25.         long long mid=(l+r)>>1;
  26.         build(2*id,l,mid);
  27.         build(2*id+1,mid+1,r);
  28.         st[id]=(st[2*id]+st[2*id+1])%MOD;
  29.     }
  30.     long long cnt(long long x, long long y)
  31.     {
  32.         return y-x+1;
  33.     }
  34.     long long sum(long long x, long long y)
  35.     {
  36.         return ((x+y)%MOD*cnt(x,y)%MOD*500000004)%MOD;
  37.     }
  38.     void push_down(long long id, long long l, long long r)
  39.     {
  40.         if(l==r) return;
  41.  
  42.         long long mid=(l+r)>>1;
  43.         long long x=lazy_x[id];
  44.         long long y=lazy_y[id];
  45.  
  46.         lazy_x[2*id]=(lazy_x[2*id]+x)%MOD;
  47.         lazy_y[2*id]=(lazy_y[2*id]+y)%MOD;
  48.         st[2*id]=(st[2*id]+y*cnt(l,mid)%MOD
  49.                   +x*sum(0,mid-l)%MOD)%MOD;
  50.  
  51.         lazy_x[2*id+1]=(lazy_x[2*id+1]+x)%MOD;
  52.         lazy_y[2*id+1]=(lazy_y[2*id+1]+y+x*(mid+1-l)%MOD)%MOD;
  53.         st[2*id+1]=(st[2*id+1]+y*cnt(mid+1,r)%MOD
  54.                     +x*sum(mid+1-l,r-l)%MOD)%MOD;
  55.  
  56.         lazy_x[id]=0;
  57.         lazy_y[id]=0;
  58.     }
  59.     void update(long long id,long long l, long long r, long long u, long long v, long long x, long long y)
  60.     {
  61.         if(l>v||r<u)
  62.         {
  63.             return;
  64.         }
  65.         if(u<=l&&r<=v)
  66.         {
  67.             long long val=(y+x*(l-u)%MOD)%MOD;
  68.  
  69.             st[id]=(st[id]+val*cnt(l,r)%MOD
  70.                     +x*sum(0,r-l)%MOD)%MOD;
  71.  
  72.             lazy_x[id]=(lazy_x[id]+x)%MOD;
  73.             lazy_y[id]=(lazy_y[id]+val)%MOD;
  74.             return;
  75.         }
  76.         long long mid=(l+r)>>1;
  77.         push_down(id,l,r);
  78.         update(2*id,l,mid,u,v,x,y);
  79.         update(2*id+1,mid+1,r,u,v,x,y);
  80.         st[id]=(st[2*id]+st[2*id+1])%MOD;
  81.     }
  82.     long long get(long long id, long long l, long long r, long long u, long long v)
  83.     {
  84.         if(l>v||r<u)
  85.         {
  86.             return 0;
  87.         }
  88.         if(u<=l&&r<=v)
  89.         {
  90.             return st[id];
  91.         }
  92.         long long mid=(l+r)>>1;
  93.         push_down(id,l,r);
  94.         return (get(2*id,l,mid,u,v)
  95.                 +get(2*id+1,mid+1,r,u,v))%MOD;
  96.     }
  97.     void update(long long u, long long v, long long x, long long y)
  98.     {
  99.         update(1,1,n,u,v,x,y);
  100.     }
  101.     long long get(long long u, long long v)
  102.     {
  103.         return get(1,1,n,u,v);
  104.     }
  105. };
  106. Segtree_lazy segtree;
  107.  
  108. int main()
  109. {
  110.     ios_base::sync_with_stdio(0);
  111.     cin.tie(0);
  112.  
  113.     cin>>n>>q;
  114.     segtree.init(n);
  115.  
  116.     for(long long i=1; i<=q; i++)
  117.     {
  118.         long long type,l,r;
  119.         cin>>type>>l>>r;
  120.         if(type==1)
  121.         {
  122.             long long x,y;
  123.             cin>>x>>y;
  124.             segtree.update(l,r,x,y);
  125.         }
  126.         else
  127.         {
  128.             cout<<segtree.get(l,r)%MOD<<"\n";
  129.         }
  130.     }
  131. }
  132.  
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oXMcNN
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!