Alcala
Lv.1
鸿鹄一再高举 天地睹方圆【第61期社区星】
获赞:5514收藏:3239浏览:121952作品收藏:1995
签名:猫站肯定不会上的了，留了两个2021年退喵时最后的作品。 有老友可以来qq:2309193203找我。
Lv.1
鸿鹄一再高举 天地睹方圆【第61期社区星】
签名:猫站肯定不会上的了，留了两个2021年退喵时最后的作品。 有老友可以来qq:2309193203找我。
在 复杂离线分治算法：值域整体分治 中回复
#include<bits/stdc++.h>
#define endl ('\n')
using namespace std;
const int maxn = 2 * 1e5 + 1e2;
int iiiii,root,n,m,a[maxn],u[maxn],size,t[maxn][2],key[maxn],siz[maxn];
void insert(int &u,int x){
if(u == 0){
u = ++size,key[u] = x,siz[u] = 1;
return;
}
int d = (x > key[u]);
insert(t[u][d],x);
siz[u]++;
}
int find(int u,int k){
int s = siz[t[u][0]];
if(k < s) return find(t[u][0],k);
if(k == s) return key[u];
return find(t[u][1],k - s - 1);
}
int order(int u,int x){
if(u == 0) return 0;
if(x <= key[u]) return order(t[u][0],x);
return siz[t[u][0]] + 1 + order(t[u][1],x);
}
int qq(int root,int x){
return find(root,order(root,x) - 1);
}
int hj(int root,int x){
return find(root,order(root,x + 1));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
int now = 1;
for(int i = 1;i <= m;i++){
cin>>a[i];
}
for(int i = 1;i <= n;i++){
cin>>u[i];
}
for(int i = 1;i <= m;i++){
insert(root,a[i]);
while(u[now] == i){
now++;
cout<<find(root,iiiii++)<<endl;
}
}
return 0;
}2021-08-08T13:26:21 点赞:0