84分呢
  • 板块P1801 黑匣子
  • 楼主liaoyichen
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/2/1 16:58
  • 上次更新2023/10/28 09:53:27
查看原帖
84分呢
486675
liaoyichen楼主2022/2/1 16:58

求助大佬调一下,赠送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;
}
2022/2/1 16:58
加载中...