都是BST的基本操作&＃xff0c;只要实现添加&＃xff0c;删除&＃xff0c;查找基本就行了。由于在同一时间在收养所里的要么都是宠物&＃xff0c;要么都是收养者&＃xff0c;因此用Splay维护在收养所中的人(宠物)的值&＃xff0c;然后根据情况插入或者查找就行了。
代码&＃xff1a;
#include#include#include#include#include#include#include#include#include#include#include#define inf 0x3f3f3f3f#define Inf 0x3FFFFFFFFFFFFFFFLL#define eps 1e-9#define pi acos(-1.0)using namespace std;typedef long long ll;const int maxn&＃61;100000&＃43;10;const int mod&＃61;1000000;int ch[maxn][2],pre[maxn],val[maxn],root,tot;void NewNode(int &rt,int fa,int v){rt&＃61;&＃43;&＃43;tot;ch[rt][0]&＃61;ch[rt][1]&＃61;0;pre[rt]&＃61;fa;val[rt]&＃61;v;}void Rotate(int x,int kind){int y&＃61;pre[x];ch[y][kind^1]&＃61;ch[x][kind];pre[ch[x][kind]]&＃61;y;if(pre[y]) ch[pre[y]][ch[pre[y]][1]&＃61;&＃61;y]&＃61;x;pre[x]&＃61;pre[y];ch[x][kind]&＃61;y;pre[y]&＃61;x;}void Splay(int rt,int goal){while(pre[rt]!&＃61;goal){int y&＃61;pre[rt];if(pre[y]&＃61;&＃61;goal)Rotate(rt,ch[y][0]&＃61;&＃61;rt);else{int kind&＃61;ch[pre[y]][0]&＃61;&＃61;y;if(ch[y][kind]&＃61;&＃61;rt){Rotate(rt,kind^1);Rotate(rt,kind);}else{Rotate(y,kind);Rotate(rt,kind);}}}if(goal&＃61;&＃61;0) root&＃61;rt;}void Insert(int v){if(root&＃61;&＃61;0){NewNode(root,0,v);return ;}int rt&＃61;root,kind;while(true){kind&＃61;val[rt]}void DelRoot(){int rt&＃61;root;if(!ch[rt][0]&&!ch[rt][1]) {root&＃61;0;return;}if(ch[rt][0]&＃61;&＃61;0){root&＃61;ch[rt][1];pre[root]&＃61;0;return ;}int rc&＃61;ch[rt][0];while(ch[rc][1])rc&＃61;ch[rc][1];Splay(rc,rt);ch[rc][1]&＃61;ch[rt][1];pre[ch[rt][1]]&＃61;rc;pre[rc]&＃61;0;root&＃61;rc;}int getminv(int v){int rt&＃61;root,kind;while(true){kind&＃61;val[rt]}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;while(~scanf("%d",&n)){int nowt,type,v;ch[0][0]&＃61;ch[0][1]&＃61;0;val[0]&＃61;0;root&＃61;tot&＃61;0;int sum&＃61;0;for(int i&＃61;0;i}
京公网安备 11010802041100号