SHARE
TWEET

Untitled

a guest Feb 29th, 2016 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int t,n,q;
  4. const int mxn=(1e5)+6;
  5. int a[mxn];
  6. long long st[mxn*4];
  7. long long su[mxn*4];
  8. long long laz[mxn*4][2];
  9.  
  10. void build(int p,int l,int r)
  11. {
  12.     if(l==r)st[p]=(a[l]*a[l]),su[p]=a[l];
  13.     else
  14.     {
  15.         int m=(l+r)/2;
  16.         st[p*2]=0;
  17.         st[p*2+1]=0;
  18.         build(p*2,l,m);
  19.         build(p*2+1,m+1,r);
  20.         st[p]=st[p*2]+st[p*2+1];
  21.         su[p]=su[p*2]+su[p*2+1];
  22.     }
  23. }
  24. //laz[p][0]: set query
  25. //laz[p][1]: add query
  26. void pros(int p,int l,int r)
  27. {
  28.     if(laz[p][0]!=0)
  29.     {
  30.         st[p]=(laz[p][0]*laz[p][0])*((r-l)+1);
  31.         su[p]=laz[p][0]*((r-l)+1);
  32.         if(l!=r)
  33.         {
  34.             laz[p*2][0]=laz[p][0];
  35.             laz[p*2][1]=0;
  36.             laz[p*2+1][0]=laz[p][0];
  37.             laz[p*2+1][1]=0;
  38.         }
  39.         laz[p][0]=0;
  40.     }
  41.     if(laz[p][1]!=0)
  42.     {
  43.         st[p]=(st[p]+(2*laz[p][1]*su[p])+(laz[p][1]*laz[p][1]*(r-l+1)));
  44.         su[p]=(su[p]+(laz[p][1]*(r-l+1)));
  45.         if(l!=r)
  46.         {
  47.             if(laz[p*2][0]!=0)
  48.                 laz[p*2][0]+=laz[p][1];
  49.             else
  50.                 laz[p*2][1]+=laz[p][1];
  51.            
  52.             if(laz[p*2+1][0]!=0)
  53.                 laz[p*2+1][0]+=laz[p][1];
  54.             else
  55.                 laz[p*2+1][1]+=laz[p][1];
  56.         }
  57.         laz[p][1]=0;
  58.     }
  59. }
  60.  
  61. void update(int p,int l,int r,int i,int j,int xx)
  62. {
  63.     pros(p,l,r);
  64.     if(r<i||l>j)return;
  65.     if(l>=i&&r<=j)
  66.     {
  67.         laz[p][1]+=xx;
  68.         pros(p,l,r);
  69.         return;
  70.     }
  71.     int m=(l+r)/2;
  72.     update(p*2,l,m,i,j,xx);
  73.     update(p*2+1,m+1,r,i,j,xx);
  74.     st[p]=st[p*2]+st[p*2+1];
  75.     su[p]=su[p*2]+su[p*2+1];
  76. }
  77.  
  78. void change(int p,int l,int r,int i,int j,int xx)
  79. {
  80.     pros(p,l,r);
  81.     if(r<i||l>j)return;
  82.     if(l>=i&&r<=j)
  83.     {
  84.         laz[p][0]=xx;
  85.         pros(p,l,r);
  86.         return;
  87.     }
  88.     int m=(l+r)/2;
  89.     change(p*2,l,m,i,j,xx);
  90.     change(p*2+1,m+1,r,i,j,xx);
  91.     st[p]=st[p*2]+st[p*2+1];
  92.     su[p]=su[p*2]+su[p*2+1];
  93. }
  94.  
  95. long long rsq(int p,int l,int r,int i,int j)
  96. {
  97.     pros(p,l,r);
  98.     if(r<i||l>j)return 0;
  99.     if(l>=i&&r<=j)return st[p];
  100.     int m=(l+r)/2;
  101.     return rsq(p*2,l,m,i,j)+rsq(p*2+1,m+1,r,i,j);
  102. }
  103.  
  104. int main()
  105. {
  106.     scanf("%d",&t);
  107.     for(int test=1;test<=t;test++)
  108.     {
  109.         st[1]=0;
  110.         scanf("%d%d",&n,&q);
  111.         for(int i=0;i<n;i++)scanf("%d",&a[i]);
  112.         build(1,0,n-1);
  113.         printf("Case %d:\n",test);
  114.         int l,r,ty,xx;
  115.         while(q--)
  116.         {
  117.             scanf("%d%d%d",&ty,&l,&r);
  118.             if(ty==0)
  119.             {
  120.                 scanf("%d",&xx);
  121.                 change(1,0,n-1,l-1,r-1,xx);
  122.             }
  123.             else if(ty==1)
  124.             {
  125.                 scanf("%d",&xx);
  126.                 update(1,0,n-1,l-1,r-1,xx);
  127.             }
  128.             else printf("%lld\n",rsq(1,0,n-1,l-1,r-1));
  129.         }
  130.     }
  131.     return 0;
  132. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top