splay求助卡常
查看原帖
splay求助卡常
236243
2018090807L楼主2022/5/29 16:26
#include<bits/stdc++.h>
#define maxn 700005
using namespace std;
int rt,sz;
int siz[maxn],rc[maxn],son[maxn][2],val[maxn],f[maxn];
int read()
{
    int out=0,flag=1;
    char c=getchar();
    while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
    while(c>=48&&c<=57)
    {
        out=out*10+c-48;
        c=getchar();
    }
    return out*flag;
}
void pushup(int x){
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+rc[x];
}
void rotate(int x){
	int fa=f[x],ffa=f[fa],k=son[fa][1]==x;
	if(ffa)son[ffa][son[ffa][1]==fa]=x;
	f[x]=ffa;
	son[fa][k]=son[x][k^1];
	f[son[x][k^1]]=fa;
	son[x][k^1]=fa;
	f[fa]=x;
	pushup(fa);
	pushup(x);
}
void splay(int x,int goal){
	if(!goal)rt=x;
	while(goal!=f[x]){
		int fa=f[x],ffa=f[fa];
		if(ffa^goal)(son[fa][1]==x)^(son[ffa][1]==fa)?rotate(fa):rotate(x);
		rotate(x);
	}
}void find(int x){
	int u=rt;
	if(!u)return;
	while(x^val[u]&&son[u][val[u]<x])u=son[u][val[u]<x];
	splay(u,0);
}int Next(int x,int f){
	find(x);
	if(val[rt]<x&&!f)return rt;
	if(val[rt]>x&&f)return rt;
	int u=son[rt][f];
	while(son[u][f^1])u=son[u][f^1];
	return u;
}void del(int x){
	int nxt=Next(x,1),lst=Next(x,0);
	splay(lst,0);
	splay(nxt,lst);
	int u=son[nxt][0];
	if(!--rc[u]){
		son[nxt][0]=0;
		splay(nxt,0);
	}else{
		splay(u,0);
	}
}
int kth(int k){
	int u=rt;
	while(1){
		int v=son[u][0];
		if(rc[u]+siz[v]<k){
			k-=rc[u]+siz[v];
			u=son[u][1];
		}else{
			if(k<=siz[v])u=v;
			else return val[u];
		}
	}
}
void insert(int x){
	int u=rt,ff=0;
	while(u&&val[u]^x){
		ff=u;
		u=son[u][val[u]<x];
	}if(u){
		rc[u]++;
	}else{
		u=++sz;
		if(ff)son[ff][val[ff]<x]=u;
		val[u]=x;
		siz[u]=1;
		rc[u]=1;
		f[u]=ff;
	}splay(u,0);
}

int main(){
	insert(-999999999);
	insert(999999999);
	int n,Max;
	scanf("%d",&n);
	Max=n;
	for(int i=1;i<=n;i++)insert(i);
	int cur=1;
	for(int i=1;i<=n;i++){
//		printf("???%d\n",Max);
		int tmp,r;
		r=read();
		r%=(siz[rt]-2);
		if(r==Max-1)tmp=siz[rt]-2-1;
		else if(r<Max)tmp=Max-r-1;
		else if(r==Max)tmp=siz[rt]-2-1;
		else tmp=siz[rt]-2-1-(r-Max);
		if(r>=Max){
			int nmd=kth(r-Max+1+1);
			printf("%d\n",nmd);
			del(nmd);
		}else{
			int xxmd=kth(siz[rt]-2-Max+r+1+1);
			printf("%d\n",xxmd);
			del(xxmd);
		}Max=tmp;
	}
	return 0;
}

TLE3个点求优化

2022/5/29 16:26
加载中...