题解 [HNOI2004]宠物收养场

解析

这题似乎是裸的平衡树\(+\)模拟...于是用\(treap\)写了个板子.

看上去,我们似乎要维护两颗树(宠物和顾客),

然而,注意到,同一时间宠物点只有一类人(或物qwq),

所以,只要判断当前宠物店和询问是否是一样,

根据题意模拟就行了.

另外,没有重复感觉比较舒服

上AC代码吧:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stdlib.h>

#define INF 0x7fffffff

#define Mod 1000000

using namespace std;

inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

	while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}

	return sum*f;

}

struct tree{int l,r,val,dat;}t[1000001];

int n,root,tot=0,ans=0;

int ok,sum=0;

inline int New(int val){

	t[++tot].val=val;t[tot].dat=rand();

	return tot;

}

inline void build(){

	New(-INF);New(INF);

	root=1;t[1].r=2;

}

inline void zig(int &p){

	int q=t[p].l;

	t[p].l=t[q].r;t[q].r=p;p=q;

} 

inline void zag(int &p){

	int q=t[p].r;

	t[p].r=t[q].l;t[q].l=p;p=q;

}

void insert(int &p,int val){

	if(!p){p=New(val);return ;}

	insert(val<t[p].val? t[p].l:t[p].r,val);

	if(t[t[p].l].dat>t[p].dat) zig(p);

	if(t[t[p].r].dat>t[p].dat) zag(p);

}

void remove(int &p,int val){

	if(!p) return ;

	if(t[p].val==val){

		if(!t[p].l&&!t[p].r){p=0;return ;}

		if(!t[p].r||t[t[p].l].dat>t[t[p].r].dat){

			zig(p);remove(t[p].r,val);

		}

		else{

			zag(p);remove(t[p].l,val);

		}

	}

	remove(val<t[p].val? t[p].l:t[p].r,val);

}

inline int getpre(int val){

	int ans=1,p=root;

	while(p){

		if(t[p].val==val) return val;

		if(t[p].val<val&&t[p].val>t[ans].val) ans=p;

		p=val<t[p].val? t[p].l:t[p].r;

	}

	return t[ans].val;

}

inline int getnext(int val){

	int ans=2,p=root;

	while(p){

		if(t[p].val==val) return val;

		if(t[p].val>val&&t[p].val<t[ans].val) ans=p;

		p=val<t[p].val? t[p].l:t[p].r;

	}

	return t[ans].val;

}

inline void find(int val){

	int l=getpre(val),r=getnext(val);

	if(l!=-INF&&val-l<=r-val){ans=(ans+val-l)%Mod;remove(root,l);sum--;}

	else{ans=(ans+r-val)%Mod;remove(root,r);sum--;}

}

int main(){

	n=read();build();

	for(int i=1;i<=n;i++){

		int x=read(),y=read();

		if(!sum){insert(root,y);sum++;ok=x;}//店里什么都没有

		else if(x==ok){insert(root,y);sum++;}//询问和店里的一样

		else find(y);//不一样,可以带走

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

题解 [HNOI2004]宠物收养场

解析

最新文章

热门文章