fork download
copy 
  1.  
  2.  
  3. 				/* RANGE INCREMENT + RANGE MIN/MAX QUERIES + ITERATIVE */
  4.  
  5. using namespace std;
  6. #include <bits/stdc++.h>
  7.  
  8. struct SegLzy{
  9. 	typedef long long ll;
  10.     #define _  j*2
  11.     #define __ j*2+1
  12.  
  13.     vector<int> S,L; ll n,h,tt;
  14.     //pass 't' as {-1,1} for {min,max} segtree
  15.     SegLzy(vector<int> ar,int t){
  16.         n=ar.size(); h=32-__builtin_clz(n); tt=-1e18*t;
  17.         S.assign(2*n,0); L.assign(n,0);
  18.         for(int i=0;i<n;i++)S[n+i]=ar[i];
  19.         for(int j=n-1;j>0;j--)S[j]=fn(S[_],S[__]);  
  20.     }
  21. 	void inline Push(long long p){
  22.         for(int i=h,j=p>>i;i>0;--i,j=p>>i)if(L[j]){
  23.             S[_] +=L[j];if(_ <n)L[_] +=L[j];
  24.             S[__]+=L[j];if(__<n)L[__]+=L[j];
  25.             L[j]=0;
  26.         } 
  27.     }
  28.     void Updt(int l,int r,int v){
  29.         ll s=l+n,e=r-1+n,j;
  30.         for(l+=n,r+=n;l<r;l/=2,r/=2){
  31.             if(l&1){S[l]+=v;if(l<n)L[l]+=v;l++;}
  32.             if(r&1){--r;S[r]+=v;if(r<n)L[r]+=v;}
  33.         }
  34.         j=s;while((j/=2)>0)S[j]=fn(S[_],S[__])+L[j];
  35.         j=e;while((j/=2)>0)S[j]=fn(S[_],S[__])+L[j];
  36.     }
  37.     long long Kqry(int l,int r){
  38.         Push(l+n); Push(r-1+n); ll res=tt;
  39.         for(l+=n,r+=n;l<r;l/=2,r/=2){
  40.             if(l&1)res=fn(res,S[l++]);
  41.             if(r&1)res=fn(res,S[--r]);
  42.         }return res;
  43.     }
  44.     inline ll fn(ll x,ll y){
  45.     	return(tt<0)?max(x,y):min(x,y);
  46.     }
  47. };
  48.  
  49. int main() {
  50.  
  51.     vector<int> a = {1,2,3,4,5,6,7,18,9,10};
  52.     SegLzy S(a,1);
  53.     cout << "Kqry [0,10) : " << S.Kqry(0,10) << endl;
  54.     cout << "Kqry [0,5)  : " << S.Kqry(0,5) << endl;
  55.     S.Updt(3,7,10);
  56.     cout << "Kqry [0,10) : " << S.Kqry(0,10) << endl;
  57.     cout << "Kqry [0,5)  : " << S.Kqry(0,5) << endl;
  58.  
  59.     return 0;
  60. }
  61.  
  62. //-----------------------------------------------------------------------------
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Kqry [0,10) : 18
Kqry [0,5)  : 5
Kqry [0,10) : 18
Kqry [0,5)  : 15
https://ideone.com/e8mUeX
RANGE INCREMENT + RANGE MIN/MAX QUERIES + ITERATIVE
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!