Guest User

Untitled

a guest
Sep 28th, 2018
115
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