| 123456 |
- #include <cstdint>
- #include <iostream>
- #include <random>
- #include <vector>
- using namespace std;struct Node{int l=0,r=0,size=0,key=0;uint32_t priority=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int m,n;cin>>m>>n;vector<int>a(m),u(n);for(int&x:a)cin>>x;for(int&x:u)cin>>x;mt19937 rng(712367);vector<Node>tr(1);auto pull=[&](int x){tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1;};auto split=[&](auto&&self,int root,int key)->pair<int,int>{if(!root)return{0,0};if(tr[root].key<=key){auto [a,b]=self(self,tr[root].r,key);tr[root].r=a;pull(root);return{root,b};}auto [a,b]=self(self,tr[root].l,key);tr[root].l=b;pull(root);return{a,root};};auto merge=[&](auto&&self,int a,int b)->int{if(!a||!b)return a?a:b;if(tr[a].priority<tr[b].priority){tr[a].r=self(self,tr[a].r,b);pull(a);return a;}tr[b].l=self(self,a,tr[b].l);pull(b);return b;};auto insert=[&](int root,int key){int z=tr.size();tr.push_back({0,0,1,key,static_cast<uint32_t>(rng())});auto [a,b]=split(split,root,key);return merge(merge,merge(merge,a,z),b);};auto kth=[&](int root,int k){while(root){int left=tr[tr[root].l].size;if(k==left+1)return tr[root].key;if(k<=left)root=tr[root].l;else k-=left+1,root=tr[root].r;}return 0;};int root=0,inserted=0;for(int i=1;i<=n;++i){while(inserted<u[i-1])root=insert(root,a[inserted++]);cout<<kth(root,i)<<'\n';}}
|
