Advertisement
hkshakib

Untitled

Mar 24th, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll mx = 1e5+10;
  5. ll arr[3*mx], tree[mx * 3], lazy[3*mx] ;
  6. ll t,n,q;
  7. void Propagation(ll node,ll b,ll e)
  8. {
  9. ll Left = node * 2 ;
  10. ll Right= node * 2 + 1 ;
  11. if(b != e)
  12. {
  13. lazy[Left] = lazy[Right] = lazy[node];
  14. }
  15. tree[node] = lazy[node]*((e - b ) + 1);
  16. lazy[node] = -1;
  17. }
  18. void init(ll node, ll b, ll e)
  19. {
  20. if (b == e)
  21. {
  22. tree[node] = 0;
  23. lazy[node] = -1 ;
  24. return;
  25. }
  26. ll Left = node * 2;
  27. ll Right = node * 2 + 1;
  28. ll mid = (b + e) / 2;
  29. init(Left, b, mid);
  30. init(Right, mid + 1, e);
  31.  
  32. }
  33. ll query(ll node, ll b, ll e, ll i, ll j)
  34. {
  35. if(lazy[node]!= -1)
  36. Propagation(node,b,e);
  37. if (i > e || j < b || b > e)
  38. return 0;
  39.  
  40. if (b >= i and e <= j)
  41. {
  42. return tree[node];
  43. }
  44.  
  45. ll Left = node << 1;
  46. ll Right = (node << 1) + 1;
  47. ll mid = (b + e) >> 1;
  48.  
  49. ll p1 = query(Left, b, mid, i, j);
  50. ll p2 = query(Right, mid + 1, e, i, j);
  51.  
  52. return p1 + p2;
  53. }
  54. void update(ll node, ll b, ll e, ll i, ll j, ll x)
  55. {
  56. if(lazy[node]!= -1)
  57. Propagation(node,b,e);
  58. if (i > e || j < b)
  59. return;
  60. ll Left = node * 2;
  61. ll Right = (node * 2) + 1;
  62. ll mid = (b + e) / 2;
  63. if (b >= i && e <= j)
  64. {
  65. tree[node] = ((e - b + 1) * x);
  66. if(b!=e)
  67. {
  68. lazy[Left] = lazy[Right] = x ;
  69. }
  70. return;
  71. }
  72. update(Left, b, mid, i, j, x);
  73. update(Right, mid + 1, e, i, j, x);
  74. tree[node] = tree[Left] + tree[Right] ;
  75. }
  76.  
  77. int main()
  78. {
  79. int cas=1;
  80. scanf("%lld",&t);
  81. while(t--)
  82. {
  83. memset(arr, 0, sizeof arr) ;
  84. memset(tree,0,sizeof tree) ;
  85. memset(lazy,-1,sizeof lazy) ;
  86. scanf("%lld%lld",&n,&q);
  87. for(int i =1 ; i<= n ; i++)
  88. {
  89. arr[i]=0;
  90. }
  91. init(1,1,n);
  92. printf("Case %d:\n",cas++);
  93. while(q--)
  94. {
  95. ll no,i,j,val;
  96. scanf("%lld",&no);
  97. if(no == 1)
  98. {
  99. scanf("%lld%lld%lld",&i,&j,&val);
  100. i++,j++;
  101. update(1,1,n,i,j,val);
  102. }
  103. else
  104. {
  105. scanf("%lld%lld",&i,&j);
  106. i++,j++;
  107. ll res = query(1,1,n,i,j);
  108. ll num = (j - i + 1);
  109. ll gcd = __gcd(res,num);
  110. if( res % num )
  111. printf("%lld/%lld\n",(res)/gcd, (num) /gcd);
  112. else
  113. printf("%lld\n",res/num);
  114. }
  115. }
  116. }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement