Advertisement
a53

Actualizare Interval, Minim Interval

a53
Aug 7th, 2017
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.92 KB | None | 0 0
  1. #include <fstream>
  2. #include <climits>
  3. #define DIM 100010
  4. #define INF INT_MAX
  5. using namespace std;
  6. ifstream f("aimi.in");
  7. ofstream g("aimi.out");
  8.  
  9. struct nod
  10. {
  11. int value,add;
  12. };
  13.  
  14. nod A[4*DIM];
  15. int n,m,a,b,t,i,minim,x;
  16.  
  17. void build(int nod,int st,int dr)
  18. {
  19. if(st==dr)
  20. {
  21. f>>A[nod].value;
  22. }
  23. else
  24. {
  25. int mid=(st+dr)/2;
  26. build(2*nod,st,mid);
  27. build(2*nod+1,mid+1,dr);
  28. A[nod].value=min(A[2*nod].value,A[2*nod+1].value);
  29. }
  30. }
  31.  
  32. void query(int nod,int st,int dr,int a,int b)
  33. {
  34. if(a<=st&&dr<=b)
  35. {
  36. minim=min(minim, A[nod].value);
  37. }
  38. else
  39. {
  40. if(A[nod].add==1)
  41. {
  42. A[2*nod].value=A[nod].value;
  43. A[2*nod].add=1;
  44. A[2*nod+1].value=A[nod].value;
  45. A[2*nod+1].add=1;
  46. A[nod].add=0;
  47. }
  48. int mid=(st+dr)/2;
  49. if(a<=mid)
  50. query(2*nod,st,mid,a,b);
  51. if(b>mid)
  52. query(2*nod+1,mid+1,dr,a,b);
  53. A[nod].value=min(A[2*nod].value,A[2*nod+1].value);
  54. }
  55. }
  56.  
  57. void update(int nod,int st,int dr,int a,int b,int x)
  58. {
  59. if(a<=st&&dr<=b)
  60. {
  61. A[nod].value=x;
  62. A[nod].add=1;
  63. }
  64. else
  65. {
  66. if(A[nod].add==1)
  67. {
  68. A[2*nod].value=A[nod].value;
  69. A[2*nod].add=1;
  70. A[2*nod+1].value=A[nod].value;
  71. A[2*nod+1].add=1;
  72. A[nod].add=0;
  73. }
  74. int mid=(st+dr)/2;
  75. if(a<=mid)
  76. update(2*nod,st,mid,a,b,x);
  77. if(b>mid)
  78. update(2*nod+1,mid+1,dr,a,b,x);
  79. A[nod].value=min(A[2*nod].value,A[2*nod+1].value);
  80. }
  81. }
  82.  
  83. int main ()
  84. {
  85. f>>n;
  86. build(1,1,n);
  87. f>>m;
  88. for(int i=1;i<=m;++i)
  89. {
  90. f>>t>>a>>b;
  91. if(t==1)
  92. minim=INF,query(1,1,n,a,b),g<<minim<<'\n';
  93. else
  94. f>>x,update(1,1,n,a,b,x);
  95. }
  96. return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement