每日总结-1月20日

数据结构进阶

• splay树
• 主席树

今日战况

前言

今天看了好长时间的splay树和主席树的相关内容，但还是看的不明白，又去看训练的题目集，发现F题又可以用set写，之后，又从伍老师那里知道了A题也可以用set写，于是，就又用set A了这两道题。

部分题目

F题: 宠物收养所

题目传送门

题目

最近，阿 Q 开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物，阿 Q 根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 a（a 是一个正整数，a < 2^31），而他也给每个处在收养所的宠物一个特点值，这样他就能够很方便的处理整个领养宠物的过程了。

宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少：

1. 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 a，那么它将会领养一只目前未被领养的宠物中特点值最接近 a 的一只宠物。任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的。如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 a-b 和 a+b，那么领养者将会领养特点值为 a-b 的那只宠物；
2. 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 a，存在两个领养者他们希望领养宠物的特点值分别为 a-b 和 a+b，那么特点值为 a-b 的那个领养者将成功领养该宠物。一个领养者领养了一个特点值为 a 的宠物，而它本身希望领养的宠物的特点值为 b，那么这个领养者的不满意程度为 |a-b|。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

输入格式

第一行为一个正整数 n，表示一年当中来到收养所的宠物和领养者的总数；

接下来的 n 行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个整数 a, b，其中 a=0 表示宠物，a=1 表示领养者，正数 b 表示宠物的特点值或是领养者希望领养宠物的特点值。

同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过 10^4 个。

输出格式

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和对 10^6 取模以后的结果。

样例

Input

5
0 2
0 4
1 3
1 2
1 5

Output

3

数据范围与提示

对于全部数据，有 1<=n<=8*10^4。

思路

这道题就是一道模拟，用set进行存储，用 lower_bound 进行查找比他大一点的，再减一就是比他小一点的。

代码

#include<cstdio>
#include<set>
using namespace std;

int n,ans=0,sipet=0,sipeo=0;
set<int> pet,peo;

inline void solve(){
	scanf("%d",&n);
	int flag,a;
	while(n--){
		scanf("%d%d",&flag,&a);
		if(flag==0){
			if(sipet>=sipeo){
				pet.emplace(a);
				++sipet;
			}
			else{
				auto it1=peo.lower_bound(a);
				if(it1==peo.end()){
					--it1;
					int jj=*it1;
					ans+=a-jj;ans%=1000000;
					--sipeo;
					peo.erase(it1);
				}
				else{
					if(it1==peo.begin()){
						int jj=*it1;
						ans+=jj-a;ans%=1000000;
						--sipeo;
						peo.erase(it1);
					}
					else{
						auto it2=it1;--it2;
						int jj=*it1,kk=*it2;
						if(a-kk<=jj-a){
							ans+=a-kk;ans%=1000000;
							--sipeo;
							peo.erase(it2);
						}
						else{
							ans+=jj-a;ans%=1000000;
							--sipeo;
							peo.erase(it1);
						}
					}
				}
			}
		}
		else{
			if(sipeo>=sipet){
				peo.emplace(a);
				++sipeo;
			}
			
			else{
				auto it1=pet.lower_bound(a);
				if(it1==pet.end()){
					--it1;
					int jj=*it1;
					ans+=a-jj;ans%=1000000;
					--sipet;
					pet.erase(it1);
				}
				else{
					if(it1==pet.begin()){
						int jj=*it1;
						ans+=jj-a;ans%=1000000;
						--sipet;
						pet.erase(it1);
					}
					else{
						auto it2=it1;--it2;
						int jj=*it1,kk=*it2;
						if(a-kk<=jj-a){
							ans+=a-kk;ans%=1000000;
							--sipet;
							pet.erase(it2);
						}
						else{
							ans+=jj-a;ans%=1000000;
							--sipet;
							pet.erase(it1);
						}
					}
				}
			}
			
		}
	}
	
	printf("%d\n",ans);
}

int main(){
	solve();
	
	return 0;
}

A题: Double Queue

题目传送门

题目

The new founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania, and using modern information technologies. As usual, each client of the bank is identified by a positive integer K and, upon arriving to the bank for some services, he or she receives a positive integer priority P. One of the inventions of the young managers of the bank shocked the software engineer of the serving system. They proposed to break the tradition by sometimes calling the serving desk with the lowest priority instead of that with the highest priority. Thus, the system will receive the following types of request:

0	The system needs to stop serving
1 K P	Add client K to the waiting list with priority P
2	Serve the client with the highest priority and drop him or her from the waiting list
3	Serve the client with the lowest priority and drop him or her from the waiting list

Your task is to help the software engineer of the bank by writing a program to implement the requested serving policy.

Input

Each line of the input contains one of the possible requests; only the last line contains the stop-request (code 0). You may assume that when there is a request to include a new client in the list (code 1), there is no other request in the list of the same client or with the same priority. An identifier K is always less than 10^6 , and a priority P is less than 10^7 . The client may arrive for being served multiple times, and each time may obtain a different priority.

Output

For each request with code 2 or 3, the program has to print, in a separate line of the standard output, the identifier of the served client. If the request arrives when the waiting list is empty, then the program prints zero (0) to the output.

Sample Input

2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

Sample Output

0
20
30
10
0

思路

可以使用 set<pair<int,int> > 进行存储数据，根据优先级进行排序，若 set< int > a，则 a.begin() 即为 a 中最小值的迭代器， a.end() - 1 即为 a 中最大值的迭代器(不越界的情况下)。

代码

#include<cstdio>
#include<set>
using namespace std;

struct P{
	int pri,num;
	friend bool operator<(P jj,P kk){
		return jj.pri<kk.pri;
	}
};
set<P> se;

inline void solve(){
	int flag;
	while(~scanf("%d",&flag)&&flag){
		if(flag==1){
			P jj;
			scanf("%d%d",&jj.num,&jj.pri);
			se.insert(jj);
		}
		else if(flag==2){
			if(se.size()==0)
				printf("0\n");
			else{
				set<P>::iterator it=se.end();--it;
				printf("%d\n",it->num);
				se.erase(it);
			}
		}
		else{
			if(se.size()==0)
				printf("0\n");
			else{
				set<P>::iterator it=se.begin();
				printf("%d\n",it->num);
				se.erase(it);
			}
		}
	}
	
	
	
}

int main(){
	solve();
	
	return 0;
}

总结

splay树和主席树确实是还没看懂，用set水了三道题，尽量掌握 set 的各种用法吧。