Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- using namespace std;
- class SegmentTree
- {
- public:
- vector <int> pozitie;
- vector <int> minim;
- void Start (int n)
- {
- pozitie.resize(n<<2);
- minim.resize(n<<2);
- fill(pozitie.begin(),pozitie.end(),0);
- for(auto &x:minim)
- x=2000000001;
- }
- void Sterge(int nod,int st,int dr,int val)
- {
- if(st==dr)
- {
- minim[nod]=2000000001;
- pozitie[nod]=0;
- return;
- }
- int mij=(st+dr)>>1;
- if(minim[nod<<1]==val)
- Sterge(nod<<1,st,mij,val);
- else
- Sterge(nod<<1|1,mij+1,dr,val);
- pozitie[nod]=pozitie[nod<<1]+pozitie[nod<<1|1];
- minim[nod]=min(minim[nod<<1],minim[nod<<1|1]);
- }
- void Update(int nod,int st,int dr,int poz,int val)
- {
- if(st==dr)
- {
- minim[nod]=val;
- pozitie[nod]=1;
- return;
- }
- int mij=(st+dr)>>1;
- if(poz<=mij)
- Update(nod<<1,st,mij,poz,val);
- else
- Update(nod<<1|1,mij+1,dr,poz,val);
- pozitie[nod]=pozitie[nod<<1]+pozitie[nod<<1|1];
- minim[nod]=min(minim[nod<<1], minim[nod<<1|1]);
- }
- int Generate_poz(int nod,int st,int dr,int k)
- {
- if(st==dr)
- return st;
- int mij=(st+dr)>>1;
- if(pozitie[nod<<1]>=k)
- return
- Generate_poz(nod<<1,st,mij,k);
- return
- Generate_poz(nod<<1|1,mij+1,dr,k-pozitie[nod<<1]);
- }
- } Arb;
- int main()
- {
- ifstream f("aesm.in");
- ofstream g("aesm.out");
- int n,m;
- f>>n;
- Arb.Start(n);
- for(int i=1;i<=n;++i)
- {
- int x;
- f>>x;
- Arb.Update(1,1,n,i,x);
- }
- f>>m;
- for(int i=1;i<=m;++i)
- {
- int tip;
- f>>tip;
- if(tip==1)
- {
- g<<Arb.minim[1]<<'\n';
- Arb.Sterge(1,1,n,Arb.minim[1]);
- }
- else
- {
- int pozitie,valoare;
- f>>pozitie>>valoare;
- Arb.Update(1,1,n,Arb.Generate_poz(1,1,n,pozitie),valoare);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement