Advertisement
a53

Actualizare Element, Stergere Minim

a53
Aug 15th, 2017
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.16 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class SegmentTree
  6. {
  7. public:
  8. vector <int> pozitie;
  9. vector <int> minim;
  10.  
  11. void Start (int n)
  12. {
  13. pozitie.resize(n<<2);
  14. minim.resize(n<<2);
  15. fill(pozitie.begin(),pozitie.end(),0);
  16. for(auto &x:minim)
  17. x=2000000001;
  18. }
  19.  
  20. void Sterge(int nod,int st,int dr,int val)
  21. {
  22. if(st==dr)
  23. {
  24. minim[nod]=2000000001;
  25. pozitie[nod]=0;
  26. return;
  27. }
  28. int mij=(st+dr)>>1;
  29. if(minim[nod<<1]==val)
  30. Sterge(nod<<1,st,mij,val);
  31. else
  32. Sterge(nod<<1|1,mij+1,dr,val);
  33. pozitie[nod]=pozitie[nod<<1]+pozitie[nod<<1|1];
  34. minim[nod]=min(minim[nod<<1],minim[nod<<1|1]);
  35. }
  36.  
  37. void Update(int nod,int st,int dr,int poz,int val)
  38. {
  39. if(st==dr)
  40. {
  41. minim[nod]=val;
  42. pozitie[nod]=1;
  43. return;
  44. }
  45. int mij=(st+dr)>>1;
  46. if(poz<=mij)
  47. Update(nod<<1,st,mij,poz,val);
  48. else
  49. Update(nod<<1|1,mij+1,dr,poz,val);
  50. pozitie[nod]=pozitie[nod<<1]+pozitie[nod<<1|1];
  51. minim[nod]=min(minim[nod<<1], minim[nod<<1|1]);
  52. }
  53.  
  54. int Generate_poz(int nod,int st,int dr,int k)
  55. {
  56. if(st==dr)
  57. return st;
  58. int mij=(st+dr)>>1;
  59. if(pozitie[nod<<1]>=k)
  60. return
  61. Generate_poz(nod<<1,st,mij,k);
  62. return
  63. Generate_poz(nod<<1|1,mij+1,dr,k-pozitie[nod<<1]);
  64. }
  65. } Arb;
  66.  
  67. int main()
  68. {
  69. ifstream f("aesm.in");
  70. ofstream g("aesm.out");
  71. int n,m;
  72. f>>n;
  73. Arb.Start(n);
  74. for(int i=1;i<=n;++i)
  75. {
  76. int x;
  77. f>>x;
  78. Arb.Update(1,1,n,i,x);
  79. }
  80. f>>m;
  81. for(int i=1;i<=m;++i)
  82. {
  83. int tip;
  84. f>>tip;
  85. if(tip==1)
  86. {
  87. g<<Arb.minim[1]<<'\n';
  88. Arb.Sterge(1,1,n,Arb.minim[1]);
  89. }
  90. else
  91. {
  92. int pozitie,valoare;
  93. f>>pozitie>>valoare;
  94. Arb.Update(1,1,n,Arb.Generate_poz(1,1,n,pozitie),valoare);
  95. }
  96. }
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement