SHARE
TWEET

Untitled

a guest Sep 28th, 2018 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************
  2.  *                   BISMILLAHIR RAHMANIR RAHIM                   *
  3.  *                     Saddam Hossain shishir                     *
  4.  *       Hajee Mohammad Danesh Science & Technology University    *
  5.  *                                                                *
  6.  ***************************************************************** */
  7. #include<iostream>
  8. #include<cstdio>
  9. #include<cstring>
  10. #include<map>
  11. #include<string>
  12. #include<set>
  13. #include<cmath>
  14. #include<cctype>
  15. #include<stack>
  16. #include<cstdlib>
  17. #include<utility>
  18. #include<vector>
  19. #include<deque>
  20. #include<queue>
  21. #include<algorithm>
  22.  
  23. #define sc scanf
  24. #define si(t) scanf("%d",&t)
  25. #define sl(t) scanf("%I64d",&t)
  26. #define sii(a,b) scanf("%d%d",&a,&b)
  27.  
  28. #define P(a) printf("%d\n",a)
  29. #define PLN(a) printf("%I64d ",a)
  30. #define pf printf
  31.  
  32. #define gcd(a,b) __gcd(a,b)
  33. #define ff first
  34. #define ss second
  35. #define pr1(a) cout<<a<<endl
  36. #define pr2(a,b) cout<<a<<" "<<b<<endl
  37. #define pb push_back
  38. #define pii pair<int,int>
  39. #define pi acos(-1.0)
  40. #define PI 3.1415926535897932385
  41. #define Sin(a) sin((pi*a)/180)
  42. #define siz 1000001
  43. #define mem(ar) memset(ar,0,sizeof ar)
  44. #define one(x) __builtin_popcount(x)
  45. typedef long long ll;
  46. using namespace std;
  47.  
  48. //int dx[]= {-1,-1,0,0,1,1};
  49. //int dy[]= {-1,0,-1,1,0,1};
  50. //int dx[]= {0,0,1,-1};/*4 side move*/
  51. //int dy[]= {-1,1,0,0};/*4 side move*/
  52. //int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
  53. //int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
  54. //int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/
  55. //int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/
  56. map<ll,bool>visi;
  57.  
  58. struct info
  59. {
  60.     ll prop,sum;
  61. } tree[3*siz],tree2[3*siz];
  62.  
  63. void update(ll node,ll b,ll e,ll i,ll j,ll x)
  64. {
  65.     ll Left,Right,mid;
  66.     if (i > e || j < b) return;
  67.     if (b >= i && e <= j)
  68.     {
  69.         tree[node].sum+=((e-b+1)*x);
  70.         tree[node].prop+=x;
  71.         return;
  72.     }
  73.     Left=node*2;
  74.     Right=(node*2)+1;
  75.     mid=(b+e)/2;
  76.     update(Left,b,mid,i,j,x);
  77.     update(Right,mid+1,e,i,j,x);
  78.     tree[node].sum=tree[Left].sum+tree[Right].sum+(e-b+1)*tree[node].prop;
  79. }
  80. void update2(ll node,ll b,ll e,ll i,ll j,ll x)
  81. {
  82.     ll Left,Right,mid;
  83.     if (i > e || j < b) return;
  84.     if (b >= i && e <= j)
  85.     {
  86.         ll rem=e-b+1;
  87.         ll sum=(rem*(2*b+rem-1))/2;
  88.         sum=sum*x;
  89.         tree2[node].sum+=sum;
  90.         tree2[node].prop+=x;
  91.         return;
  92.     }
  93.     Left=node*2;
  94.     Right=(node*2)+1;
  95.     mid=(b+e)/2;
  96.     update2(Left,b,mid,i,j,x);
  97.     update2(Right,mid+1,e,i,j,x);
  98.     ll rem=e-b+1;
  99.  
  100.     ll sum=(rem*(2*b+rem-1))/2;
  101.  
  102.     tree2[node].sum=tree2[Left].sum+tree2[Right].sum+sum*tree2[node].prop;
  103. }
  104. ll query2(ll node,ll b,ll e,ll i,ll j,ll carry=0)
  105. {
  106.     ll Left,Right,mid,p1,p2;
  107.     if (i > e || j < b) return 0;
  108.     if(b>=i && e<=j)
  109.         return tree[node].sum+carry*(e-b+1);
  110.     Left=node<<1;
  111.     Right=(node<<1)+1;
  112.     mid=(b+e)>>1;
  113.  
  114.     p1 = query2(Left, b,mid, i, j, carry+tree[node].prop);
  115.     p2 = query2(Right, mid+1, e, i, j,carry+tree[node].prop);
  116.     return p1+p2;
  117. }
  118. ll query3(ll node,ll b,ll e,ll i,ll j,ll carry=0)
  119. {
  120.     ll Left,Right,mid,p1,p2;
  121.     if (i > e || j < b) return 0;
  122.     if(b>=i && e<=j)
  123.     {
  124.  
  125.         ll rem=e-b+1;
  126.  
  127.         ll sum=(rem*(2*b+rem-1))/2;
  128.  
  129.         sum=sum*carry;
  130.  
  131.         return tree2[node].sum+sum;
  132.     }
  133.     Left=node<<1;
  134.     Right=(node<<1)+1;
  135.     mid=(b+e)>>1;
  136.     p1 = query3(Left, b,mid, i, j, carry+tree2[node].prop);
  137.     p2 = query3(Right, mid+1, e, i, j,carry+tree2[node].prop);
  138.  
  139.     return p1+p2;
  140. }
  141. int main()
  142. {
  143.     //freopen("input.txt","r",stdin);
  144.     //freopen("output.txt","w",stdout);
  145.     ll  i,j,n,m,a,c,b,d,ck,t,r,x,y,ans,ans2,rem,cnt,lo,hi,sum,cs=1;
  146.     char str[100];
  147.     scanf("%lld",&t);
  148.     while(t--)
  149.     {
  150.         printf("Case %lld:\n",cs++);
  151.         scanf("%lld %lld",&n,&m);
  152.         for(i=0; i<=3*n; i++)
  153.         {
  154.             tree[i].sum=tree2[i].sum=0;
  155.             tree[i].prop=tree2[i].prop=0;
  156.         }
  157.         for(i=1; i<=n; i++)
  158.         {
  159.             update(1,1,n,i,i,100);
  160.             update2(1,1,n,i,i,100);
  161.         }
  162.         while(m--)
  163.         {
  164.             scanf("%s",str);
  165.             if(str[0]=='q')
  166.             {
  167.                 scanf("%lld%lld",&x,&y);
  168.                 ans=query3(1,1,n,x,y);
  169.                 ans2=query2(1,1,n,x,y);
  170.                 // cout<<ans<<" ans "<<ans2<<endl;
  171.                 ans=ans-ans2*(x-1);
  172.                 printf("%lld\n",ans);
  173.             }
  174.             else
  175.             {
  176.                 scanf("%lld%lld%lld",&x,&y,&c);
  177.                 update(1,1,n,x,y,c);
  178.                 update2(1,1,n,x,y,c);
  179.             }
  180.         }
  181.     }
  182. }
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
 
Top