求助大佬调一下,赠送2关注
样例也下了,拍了好久
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct Tree{
int l,r,val,key,cnt,size;
#define l(x) a[x].l
#define r(x) a[x].r
#define val(x) a[x].val
#define key(x) a[x].key
#define cnt(x) a[x].cnt
#define size(x) a[x].size
}a[N];
int tot,root,n,m,cnt=0,now=1,INF=1e9+7;
int a1[N],u1[N];
inline int read()
{ register int f=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{ if(ch=='-')
{ w=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{ f=f*10+ch-'0';
ch=getchar();
}
return f*w;
}
int new1(int v){
val(++tot)=v;
key(tot)=rand();
cnt(tot)=size(tot)=1;
return tot;
}
void update1(int pos){
size(pos)=size(l(pos))+size(r(pos))+cnt(pos);
return;
}
void build(){
new1(-INF);
new1(INF);
root=1;
r(1)=2;
update1(root);
return;
}
int rankval(int pos,int rankx){
if(pos==0){
return INF;
}
if(size(l(pos))>=rankx){
return rankval(l(pos),rankx);
}
else if(size(l(pos))+cnt(pos)>=rankx){
return val(pos);
}
else{
return rankval(r(pos),rankx-size(l(pos))-cnt(pos));
}
}
void zig(int &p){
int p2=l(p);
l(p)=r(p2);
r(p2)=p;
p=p2;
update1(r(p));
update1(p);
return;
}
void zag(int &p){
int p2=r(p);
r(p)=l(p2);
l(p2)=p;
p=p2;
update1(l(p));
update1(p);
return;
}
void Insert(int &p,int v){
if(!p){
p=new1(v);
return;
}
if(val(p)==v){
cnt(p)++;
update1(p);
return;
}
if(v<val(p)){
Insert(l(p),v);
if(key(p)<key(l(p))){
zig(p);
}
}
else{
Insert(r(p),v);
if(key(p)<key(r(p))){
zag(p);
}
}
update1(p);
return;
}
signed main(){
build();
n=read();m=read();
for(int i=1;i<=n;i++){
a1[i]=read();
}
for(int i=1;i<=m;i++){
u1[i]=read();
}
for(int i=1;i<=n;i++){
Insert(root,a1[i]);
while(u1[now]==i){
cnt++;now++;
printf("%lld\n",rankval(root,cnt+1));
}
}
return 0;
}