竞赛讨论区 > 线段树维护最小值先查右边查不到就查左边然后把点更新为Inf
头像
_Ymir_
发布于 2019-08-24 10:40
+ 关注

线段树维护最小值先查右边查不到就查左边然后把点更新为Inf

#include<stdio.h>
#include<queue>
#include<string.h> 
#define Max 1000100
#define inf 0x3f3f3f3f

using namespace std;

int max(int x,int y){if(x>y) return x;return y;}
int min(int x,int y){if(x>y) return y;return x;}
int Hash[Max];

int n;
int t[Max*4];
int a[Max];
inline void push_up(int p)
{
	t[p]=min(t[p<<1],t[p<<1|1]);
}
void build(int o,int l,int r)  //建立线段树 
{
	
	if(l==r)
	{
		t[o]=l;
		return; 
	}
	int mid=(l+r)>>1;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	push_up(o);
}
void update(int o,int l,int r,int p) //把p位置变成inf 
{
	if(l==r){t[o]=inf;return;}
	else
	{
		int m=(l+r)>>1;
		if(p<=m) update(o<<1,l,m,p);
		else update(o<<1|1,m+1,r,p);
		push_up(o);
	}
}
int query(int o,int l,int r,int nowl,int nowr)  //查询 
{
	if(nowl<=l&&r<=nowr) return t[o];
	int m=(l+r)>>1;
	int ans=inf;
	if(nowl<=m) ans=query(o<<1,l,m,nowl,nowr);
	if(nowr>m) ans =min(ans,query(o<<1|1,m+1,r,nowl,nowr));
	return ans;
}
void insert(int x)
{
	int temp=x%n+1;  //1到n 
	int ans=query(1,1,n,temp,n);  //找到右边最小 
	if(ans==inf)  //如果都是inf 表示不存在 
		ans=query(1,1,n,1,temp); //再找一次 
	Hash[ans-1]=x;
	update(1,1,n,ans);
	return;
}

int main()
{
	int x;
	scanf("%d",&n);
	build(1,1,n);
	for(int i=0;i<n;i++) 
	{
		scanf("%d",&x);
		insert(x);
	}
	for(int i=0;i<n;i++)
	{
		printf("%d",Hash[i]);
		if(i!=n-1) printf(" ");
		else printf("\n");
	}
	return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐