fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /////////////////// TYPES & MACROS ///////////////////////////////
  4. #define INFLL 0x3fffffffffffffffLL
  5. #define INF 0x3fffffff
  6. #define mp make_pair
  7. #define eb emplace_back
  8. #define pb push_back
  9. #define all(x) x.begin(),x.end()
  10. #define exist(s,e) (s.find(e)!=s.end())
  11. typedef long long int ll;
  12. typedef unsigned long long int ull;
  13. typedef long double ld;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. const ll MOD=1e9+7;
  17. /////////////////// DEBUG MODE ///////////////////////////////////
  18. #define D(x) cerr<<"DEBUG: "<<#x<<" is: "<<x<<'\n'
  19. #define error(args...) {string _s=#args; replace(all(_s),',',' ');\
  20. stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
  21. void err(istream_iterator<string> it) {}
  22. template<typename T, typename... Args>
  23. void err(istream_iterator<string> it, T a, Args... args) {
  24. 	cerr << *it << " = " << a << endl;
  25. 	err(++it, args...);
  26. }
  27. /////////////////// GLOBAL VARIABLES /////////////////////////////
  28. vector<vector<int>> adj; vector<bool> vis; vector<int> color;
  29.  
  30. /////////////////// FUNCTIONS ////////////////////////////////////
  31. template<class T>
  32. T maxx(T a, T b) {return a>b?a:b;}
  33. template<typename T, typename... Args>
  34. T maxx(T a, T b, Args... args){return maxx(a>b?a:b, args...);}
  35. ll mexp(ll x, ll n, ll m){
  36.   ll res=1;  while(n){if(n&1) res=(res*x)%m;n>>=1; x=((x%m)*(x%m))%m;}
  37.   return res;
  38. }
  39. double pow(double a, int n) {
  40.   if(n == 0) return 1;if(n == 1) return a;
  41.   double t = pow(a, n/2);return t * t * pow(a, n%2);
  42. }
  43. typedef struct SegmentTree{
  44.    vector<int> tree, udp; int orgsize;
  45.   /******************FUNCTIONS******************
  46.   SegmentTree(vector<int>);                       //NECESSARY, CALLS BUILD
  47.   void build(int cur,int s, int e, vector<int>);  //CHANGE NODE FUNCTION
  48.   void update(int s, int e, int val);             //NECESSARY
  49.   void u(int cur, int ts,int te, int s, int e, int val);
  50.   ll query(int s,int e);
  51.   ll q(int cur,int ts, int te, int s, int e);	**/
  52.   /******************BUILD***********************/
  53.   SegmentTree(vector<int>& list){ 								//CONSTRUCTOR
  54.     orgsize=list.size();
  55.     int size=((int)(pow(2,31-__builtin_clz(orgsize))))<<1;
  56.     tree.resize(size); udp.assign(size,0); build(1,0,orgsize-1,list);
  57.   }
  58.   void build(int cur, int s, int e, vector<int>& list){
  59.     if(s==e){ tree[cur]=list[s]; return ;}
  60.     else{
  61.       int mid=(s+e)/2;
  62.       build(cur<<1,s,mid,list); build((cur<<1)+1,mid+1,e,list);
  63.       tree[cur]= tree[cur<<1]+tree[(cur<<1)+1];     //NODE FUNCTION
  64.     }
  65.   }
  66.   /***************  UPDATE  **************************/
  67.   void update(int s, int e, int val){ update(1,0,orgsize-1,s,e,val);}
  68.   void update(int cur, int ts, int te, int s, int e, int val){
  69.     if(ts>=s && te<=e) udp[cur]+=val;
  70.     else{
  71.       tree[cur]+=(min(te,e)-max(ts,s)+1)*val;      //NODE FUNCTION
  72.       int mid=(ts+te)/2;
  73.       if(mid>=s && ts<=e) update(cur<<1,ts,mid,s,e,val);
  74.       if(mid+1<=e && te>=s) update((cur<<1)+1,mid+1,te,s,e,val);
  75.     }
  76.   }
  77.   /***************  QUERY ***************************/
  78.   ll query(int s, int e){return q(1,0,orgsize-1,s,e);}
  79.   ll q(int cur, int ts,int te, int s, int e){
  80.     if(ts>=s && te<=e){
  81.       if(udp[cur]!=0){
  82.         tree[cur]+=(te-ts+1)*udp[cur];            //NODE FUNCTION
  83.         if(2*cur < udp.size()){
  84.           udp[cur<<1]+=udp[cur];
  85.           udp[(cur<<1)+1]+=udp[cur];
  86.         }
  87.         udp[cur]=0;
  88.       }
  89.       return tree[cur];
  90.     }
  91.     else{
  92.       tree[cur]+=(te-ts+1)*udp[cur];
  93.       if((cur<<1) < udp.size()){
  94.         udp[cur<<1]+=udp[cur];
  95.         udp[(cur<<1)+1]+=udp[cur];
  96.       }
  97.       udp[cur]=0;
  98.       ll temp=0;
  99. 			int mid=(ts+te)/2;
  100.       if(mid>=s && ts<=e) temp+=q(cur<<1,ts,mid,s,e);
  101.       if(mid+1<=e && te>=s) temp+=q((cur<<1)+1,mid+1,te,s,e);
  102.       return temp;
  103.     }
  104.   }
  105. } ST;
  106. /////////////////// MAIN STARTS //////////////////////////////////
  107. int main(){
  108.   ios::sync_with_stdio(0);  cin.tie(0);   cout<<fixed; cerr<<fixed;
  109.   cout<<setprecision(3); cerr<<setprecision(3);
  110.   #ifdef DEBUG
  111.   freopen("ip.txt","r",stdin); //freopen("op.txt","w",stdout);
  112.   clock_t tStart = clock();
  113.   #endif
  114.  
  115. 	ll t; for(cin>>t;t>0;--t){
  116. 		ll n,c; cin>>n>>c;
  117. 		int arr[n]; memset(arr,0,sizeof(arr));
  118. 		vector<int> v(arr,arr+n);
  119. 		ST st(v);
  120. 		for(;c>0;--c){
  121. 			int choice,p,q,val; cin>>choice>>p>>q;
  122. 			if(choice==0) {cin>>val; st.update(p-1,q-1,val);}
  123. 			else{ cout<<st.query(p-1,q-1)<<'\n';}
  124. 		}
  125. 	}
  126.  
  127. 	#ifdef DEBUG
  128. 	cerr<<"\nExecution time: "<<(((double)clock() - tStart)/CLOCKS_PER_SEC)*1000<<"ms.\n";
  129. 	#endif
  130.   return 0;
  131. }
  132.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin 
1
5000 7
0 2 4 26
0 4 8 800000
0 4 1000 500454
1 8 8
0 5 7 14
1 4 8
1 1 8
stdout 
1300454
6502338
6502390
https://ideone.com/1bfAaO
language:
C++14 (gcc 8.3)
created:
6 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!