SPOJ Problem:- HORRIBLE - Horrible Queries Solution

Copy the code to your IDE for better reading then read the explanations from comment lines in code. Also please send your feed-backs. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

//NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- HORRIBLE - Horrible Queries #include<bits/stdc++.h> #define ll long long using namespace std; vector <ll> tree(800050);//,kk=0; vector <ll> lazy(800050); /*In update function I have avoided updating whole tree, if in any case a node with all its children needs to be updated then I do not go to its children for update, I simply store the value to be updated in same node of lazy vector. And when other update request comes where I need to update only one child of same node, then I add (r-l+1)*value of lazy node to tree node((r-l+1) is the range covered under that node) & add value to be updated in children of node in lazy vector.*/ void lazyupdate(ll l,ll r,ll p,ll q,ll pos,ll v) { if(lazy[pos]) { tree[pos]+=(r-l+1)*lazy[pos]; lazy[pos*2]+=lazy[pos]; lazy[pos*2+1]+=lazy[pos]; lazy[pos]=0; } if(q<l||p>r) return; if(p<=l&&r<=q) { tree[pos]+=(r-l+1)*v; lazy[pos*2]+=v;lazy[pos*2+1]+=v; return; } ll mid=(l+r)/2; lazyupdate(l,mid,p,q,pos*2,v); lazyupdate(mid+1,r,p,q,pos*2+1,v); tree[pos]=tree[pos*2]+tree[pos*2+1];//cout<<"ll "<<kk<<"_ll"; } ll search(ll l,ll r,ll p,ll q,ll pos) { if(lazy[pos]) { tree[pos]+=(r-l+1)*lazy[pos]; lazy[pos*2]+=lazy[pos]; lazy[pos*2+1]+=lazy[pos]; lazy[pos]=0; } if(q<l||p>r)return 0;//INT_MIN; if(p<=l&&r<=q) { return tree[pos]; } ll mid=(l+r)/2; return (search(l,mid,p,q,pos*2)+search(mid+1,r,p,q,pos*2+1)); } int main() { ll t; cin>>t; while(t--) { ll c,n; cin>>n>>c; //ll a[n]; //memset(a,0,sizeof(a)); //memset(lazy,0,sizeof(lazy));//cout<<lazy[0]<<"jbjjbjb"; lazy.assign(800050,0); tree.assign(800050,0); //memset(tree,0,sizeof(tree)); //update(0,n-1,0,n-1,1,0); while(c--) { bool f; cin>>f; if(f==0) {//cout<<"\nhi\n"; ll p,q,v; cin>>p>>q>>v;//++kk; lazyupdate(0,n-1,p-1,q-1,1,v); //for(ll i=0;i<16;i++)cout<<i<<"/"<<tree[i]<<" .";cout<<"\n"; //for(ll i=0;i<16;i++)cout<<i<<"/"<<lazy[i]<<" .";cout<<"\n"; } else { ll p,q; cin>>p>>q; cout<<search(0,n-1,p-1,q-1,1)<<"\n"; } } } return 0; }