fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5;
  4. long long n,q;
  5. struct Segment_tree
  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.     long long cnt(long long l, long long r)
  19.     {
  20.         return r-l+1;
  21.     }
  22.     long long sum(long long l, long long r)
  23.     {
  24.         return (l+r)*cnt(l,r)/2;
  25.     }
  26.     void push_down(long long id, long long l, long long r)
  27.     {
  28.         if(l==r) return;
  29.  
  30.         long long mid = (l+r)>>1;
  31.         long long x = lazy_x[id];
  32.         long long y = lazy_y[id];
  33.  
  34.         lazy_x[2*id] += x;
  35.         lazy_y[2*id] += y;
  36.  
  37.         lazy_x[2*id+1] += x;
  38.         lazy_y[2*id+1] += y;
  39.  
  40.         st[2*id] += x*cnt(l,mid)+y*sum(l,mid);
  41.         st[2*id+1] += x*cnt(mid+1,r)+y*sum(mid+1,r);
  42.  
  43.         lazy_x[id]=0;
  44.         lazy_y[id]=0;
  45.     }
  46.     void update(long long id, long long l, long long r, long long u, long long v, long long x, long long y)
  47.     {
  48.         if(l>v||r<u) return;
  49.         if(u<=l&&r<=v)
  50.         {
  51.             long long val=x-u*y;
  52.  
  53.             st[id] += val*cnt(l,r)+y*sum(l,r);
  54.  
  55.             lazy_x[id] += val;
  56.             lazy_y[id] += y;
  57.  
  58.             return;
  59.         }
  60.         push_down(id,l,r);
  61.         long long mid = (l+r)>>1;
  62.         update(2*id,l,mid,u,v,x,y);
  63.         update(2*id+1,mid+1,r,u,v,x,y);
  64.         st[id]=st[2*id]+st[2*id+1];
  65.     }
  66.     long long get(long long id, long long l, long long r, long long u, long long v)
  67.     {
  68.         if(l>v||r<u) return 0;
  69.         if(u<=l&&r<=v)
  70.         {
  71.             return st[id];
  72.         }
  73.         push_down(id,l,r);
  74.         long long mid = (l+r)>>1;
  75.         return get(2*id,l,mid,u,v)+get(2*id+1,mid+1,r,u,v);
  76.     }
  77.     void update(long long u, long long v, long long x, long long y)
  78.     {
  79.         update(1,1,n,u,v,x,y);
  80.     }
  81.     long long get(long long u, long long v)
  82.     {
  83.         return get(1,1,n,u,v);
  84.     }
  85. };
  86. Segment_tree segtree;
  87. int main()
  88. {
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(0);
  91.  
  92.     cin >> n >> q;
  93.     segtree.init(n);
  94.  
  95.     for(long long i=1; i<=q; i++)
  96.     {
  97.         long long num,l,r;
  98.         cin >> num >> l >> r;
  99.         if(num==1)
  100.         {
  101.             long long x,y;
  102.             cin >> x >> y;
  103.             segtree.update(l,r,x,y);
  104.         }
  105.         else
  106.         {
  107.             cout << segtree.get(l,r) << "\n";
  108.         }
  109.     }
  110. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L7u4Ww
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!