Advertisement
Guest User

Untitled

a guest
Feb 16th, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long int tree[400001],propagate[400001];
  4. void lazy(long long int node ,long long int a,long long int b)
  5. {
  6. tree[node]=(propagate[node]*(b-a+1));
  7. if(a!=b)
  8. {
  9. propagate[2*node]=propagate[node];
  10. propagate[(2*node)+1]=propagate[node];
  11. }
  12. propagate[node]=-1;
  13. }
  14. void update(long long int node,long long int a,long long int b,long long int x,long long int y,long long int value)
  15. {
  16. if(propagate[node]!=-1)
  17. {
  18. lazy(node,a,b);
  19. }
  20. if(b<x||a>y)
  21. {
  22. return ;
  23. }
  24. if(a>=x&&b<=y)
  25. {
  26. tree[node]=value*(b-a+1);
  27. if(a!=b)
  28. {
  29. propagate[2*node]=value;
  30. propagate[(2*node)+1]=value;
  31. }
  32. return;
  33. }
  34. long long int mid;
  35. mid=(a+b)/2;
  36. update(2*node,a,mid,x,y,value);
  37. update((2*node)+1,mid+1,b,x,y,value);
  38. tree[node]=tree[2*node]+tree[(2*node)+1];
  39. }
  40. long long int query(long long int node,long long int a,long long int b,long long int x,long long int y)
  41. {
  42. if(propagate[node]!=-1)
  43. {
  44. lazy(node,a,b);
  45. }
  46. if(b<x||a>y)
  47. {
  48. return 0;
  49. }
  50. if(a>=x&&b<=y)
  51. {
  52. return tree[node];
  53. }
  54. long long int mid,p1,p2;
  55. mid=(a+b)/2;
  56. p1=query(2*node,a,mid,x,y);
  57. p2=query((2*node)+1,mid+1,b,x,y);
  58. return p1+p2;
  59. }
  60. int main ()
  61. {
  62. long long int n,i,a,b,j,k,x,y,z,p,l;
  63. scanf("%lld",&n);
  64. for(i=1;i<=n;i++)
  65. {
  66. memset(propagate,-1,sizeof(propagate));
  67. memset(tree,0,sizeof(tree));
  68. scanf("%lld %lld",&a,&b);
  69. printf("Case %lld:\n",i);
  70. for(j=1;j<=b;j++)
  71. {
  72. scanf("%lld",&k);
  73. if(k==1)
  74. {
  75. scanf("%lld %lld %lld",&x,&y,&z);
  76. update(1,1,a,x+1,y+1,z);
  77. }
  78. else
  79. {
  80. scanf("%lld %lld",&x,&y);
  81. p=query(1,1,a,x+1,y+1);
  82. l=__gcd(y-x+1,p);
  83. if((y-x+1)/l==1)
  84. {
  85. printf("%lld\n",p/l);
  86. }
  87. else
  88. {
  89. printf("%lld/%lld\n",p/l,(y-x+1)/l);
  90. }
  91. }
  92. }
  93. }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement