Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int n,q;
- struct node{
- node *left,*right;
- ll lazy,sum;
- node(){
- left = right = NULL;
- lazy = sum = 0;
- }
- }*root;
- ll Sum(ll l,ll r){
- return (r*(r+1))/2 - (l*(l-1))/2;
- }
- void checkLazy(node *curr,ll b,ll e){
- if(curr->lazy!=0){
- if(b!=e){
- int mid = (b+e)>>1;
- if(!curr->left)curr->left = new node();
- if(!curr->right)curr->right = new node();
- curr->left->sum-=(curr->lazy*(ll)(mid-b+1));
- curr->right->sum-=(curr->lazy*(ll)(e-mid));
- curr->left->lazy+=curr->lazy;
- curr->right->lazy+=curr->lazy;
- }
- curr->lazy = 0;
- }
- }
- void update(node *curr,ll b,ll e,ll l,ll r,ll val){
- checkLazy(curr,b,e);
- if(l>e||b>r)return ;
- if(b>=l&&e<=r){
- curr->sum-=(val*(ll)(e-b+1));
- curr->lazy+=val;
- return ;
- }
- if(!curr->left)curr->left = new node();
- if(!curr->right)curr->right = new node();
- int mid = (b+e)>>1;
- update(curr->left,b,mid,l,r,val);
- update(curr->right,mid+1,e,l,r,val);
- curr->sum = curr->left->sum + curr->right->sum;
- }
- ll query(node *curr,ll b,ll e,ll l,ll r){
- checkLazy(curr,b,e);
- if(b>r||l>e)return 0;
- if(b>=l&&e<=r)return curr->sum;
- if(!curr->left)curr->left = new node();
- if(!curr->right)curr->right = new node();
- int mid = (b+e)>>1;
- ll p1 = query(curr->left,b,mid,l,r);
- ll p2 = query(curr->right,mid+1,e,l,r);
- return p1 + p2;
- }
- int main()
- {
- ///booster()
- ///read("input.txt");
- scani2(n,q);
- root = new node();
- while(q--){
- int c,l,r;
- scani3(c,l,r);
- if(c==1){
- int v;
- scani(v);
- update(root,1,MAX,l,r,v);
- }
- else printf("%lld\n",Sum(l,r) + query(root,1,MAX,l,r));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement