记录编号	192407	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]排名系统	最终得分	100
用户昵称	yyy	是否通过	通过
代码语言	C++	运行时间	2.476 s
提交时间	2015-10-10 20:55:35	内存使用	38.46 MiB

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <time.h>
 
using std::string;
 
typedef long long Long;
 
std::map<string,int> node;
 
namespace output
{
	struct node
	{
		string s;
		int n;
		Long val;
		node(string ss,int nn,Long vval)
		{
			s = ss;
			n = nn;
			val = vval;
		}
		
		node()
		{}
		
		bool operator<(const node & b)const
		{
			if(val == b.val)
				return n < b.n;
			return val < b.val;
		}
	};
	std::vector<node> vec;
	
	void output()
	{
		std::sort(vec.begin(),vec.end());
		for(int i = 0;i < vec.size();i++)
		{
			if(i == 0)
				printf("%s",vec[i].s.c_str());
			else printf(" %s",vec[i].s.c_str());
		}
		printf("\n");
	}
}
 
const int N = 500000;
 
namespace splay
{
	struct Int
	{
		Long val;
		int time;
		
		bool operator < (const Int & b)const
		{
			if(val == b.val)
				return time < b.time;
			return val < b.val;
		}
		
		bool operator > (const Int & b)const
		{
			if(val == b.val)
				return time > b.time;
			return val > b.val;
		}
		
		bool operator == (const Int & b)const
		{
			return val == b.val && time == b.time;
		}
		
		bool operator != (const Int & b)const
		{
			return val != b.val || time != b.time;
		}
		
		Int(Long a,int b)
		{
			val = a;
			time = b;
		}
		Int()
		{}
		
	};
	
	struct node
	{
		string name;
		Int val;
		int son[2];
		int size;
		int is_right;
		int father;
		bool lazy;
	};
	
	int tot = 0;
	node nodes[2 * N + 100];
	
	#define LC(a) nodes[a].son[0]
	#define RC(a) nodes[a].son[1]
	#define SIZE(a) nodes[a].size
	#define VAL(a) nodes[a].val
	#define TIME(a) hash::time_in[nodes[a].name]
	#define FATHER_ME(a) nodes[nodes[a].father].son[nodes[a].is_right]
	
	int root = 0;
	
	string now_name;
	int newnode(Long val,int ti)
	{
		tot++;
		nodes[tot].name = now_name;
		nodes[tot].val = Int(val,ti);
		nodes[tot].size = 1;
		return tot;
	}
	
	void updata(int d)
	{
		if(!d)
			return;
		if(nodes[d].lazy)
			SIZE(d) = SIZE(LC(d)) + SIZE(RC(d));
		else SIZE(d) = SIZE(LC(d)) + SIZE(RC(d)) + 1;
	}
	
	void add(int & d,Long val,int is_right,const int & ti,const int & fat = 0)
	{
		if(!d)
		{
			d = newnode(val,ti);
			nodes[d].is_right = is_right;
			nodes[d].father = fat;
			return;
		}
		
		if(Int(val,ti) > VAL(d))
			add(RC(d),val,1,ti,d);
		else add(LC(d),val,0,ti,d);
		
		updata(d);
	}
	
	void r_r(int f)
	{
		if(!f)
			return;
		int s = nodes[f].son[0];
		int b = nodes[s].son[1];
			 
		if(f == root)
			root = s;
		else FATHER_ME(f) = s;
		
		nodes[s].is_right = nodes[f].is_right;
		nodes[s].father = nodes[f].father;
		
		nodes[f].father = s;
		nodes[f].is_right = 1;
		nodes[s].son[1] = f;
		
		nodes[b].father = f;
		nodes[b].is_right = 0;
		nodes[f].son[0] = b;
		
		updata(f);
		updata(s);
	}
	
	void l_r(int f)
	{
		if(!f)
			return;
		int s = nodes[f].son[1];
		int b = nodes[s].son[0];
			 
		if(f == root)
			root = s;
		else FATHER_ME(f) = s;
		
		nodes[s].is_right = nodes[f].is_right;
		nodes[s].father = nodes[f].father;
		
		nodes[f].father = s;
		nodes[f].is_right = 0;
		nodes[s].son[0] = f;
		
		nodes[b].father = f;
		nodes[b].is_right = 1;
		nodes[f].son[1] = b;
		
		updata(f);
		updata(s);
	}
	
	void del(int d)
	{
		if(!d)
			return;
		nodes[d].lazy = true;
		
		updata(d);
		
		int f = nodes[d].father;
		while(f)
		{
			updata(f);
			f = nodes[f].father;
		}
	}
	
	int find_kth(int d,int k,int f = 0)
	{
		if(!d)
			return 0;
		if(nodes[d].lazy)
		{
			if(k <= SIZE(LC(d)))
				return find_kth(LC(d),k);
			return find_kth(RC(d),k - SIZE(LC(d)),d);
		}
		if(SIZE(LC(d)) == k - 1)
			return d;
		if(k <= SIZE(LC(d)))
			return find_kth(LC(d),k);
		return find_kth(RC(d),k - SIZE(LC(d)) - 1);
	}
	
	int find_num(int d,Long val,int ti)
	{
		if(!d)
			return 0;
		int sz = 0;
		Int v = Int(val,ti);
		while(nodes[d].val != v)
		{
			if(v > nodes[d].val)
			{
				sz += SIZE(LC(d)) + 1;
				if(nodes[d].lazy)
					sz--;
				d = RC(d);
			}
			else d = LC(d);
		}
		sz += SIZE(LC(d)) + 1;
		if(nodes[d].lazy)
			sz--;
		return sz;
	}
	
	void rot(int a)
	{
		if(!a)
			return;
		if(nodes[a].is_right)
			l_r(nodes[a].father);
		else r_r(nodes[a].father);
	}
	
	void splay(int a)
	{
		if(!a)
			return;
		while(a != root)
		{
			if(nodes[a].is_right != nodes[nodes[a].father].is_right)
			{
				rot(a);
				rot(a);
			}
			else 
			{
				rot(nodes[a].father);
				rot(a);
			}
		}
	}
};
 
char str[20]; 
 
int main()
{
	{
		int _q=10<<20;
		char *_p=(char*)malloc(_q)+_q;
		__asm__("movl %0, %%esp\n"::"r"(_p));
	}
	
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout);
	
	int n = 0;
	scanf("%d",&n);
	
	char c = 0;
	int op = 0;
	int num = 0;
	int re = 0;
	int m = 0;
	Long Lnum = 0LL;
	int tt = 0;
	string nm;
	for(int i = 0;i < n;i++)
	{
		do
		{
			c = getchar();
		}
		while(c == ' ' || c == '\n' || c == '\t');
	
		if(c == '?')
		{
			c = getchar();
			if(c >= '0' && c <= '9')
				op = 1;//给定排名问名字 
			else op = 2;//给定名字问排名 
			
			ungetc(c,stdin);
		}
		else op = 3;//改分数
		
		if(op == 1)
		{
			scanf("%d",&num);
			//continue;
			output::vec.clear();
			re = 0;
			for(int p = num;p < num + 10;p++)
			{
				if(p > splay::nodes[splay::root].size)
					break;
				if(re == 0)
					re = splay::find_kth(splay::root,p);
				else re = splay::find_kth(splay::nodes[re].son[1],1);
				splay::splay(re);
				
				output::vec.push_back(output::node(splay::nodes[re].name,splay::nodes[re].val.time,splay::nodes[re].val.val));
			}
			output::output();
		}
		else if(op == 2)
		{
			scanf("%s",str);
			//continue;
			int hh = node[string(str)];
			splay::splay(hh);
			Lnum = splay::nodes[hh].val.val;
			tt = splay::nodes[hh].val.time;
			printf("%d\n",splay::find_num(splay::root,Lnum,tt));
		}
		else
		{
			scanf("%s",str);
			std::cin>>Lnum;
			Lnum = -Lnum;
			nm = str;
			m = node[nm];
			splay::del(m);
			if(m)
				splay::splay(m);
			splay::now_name = nm;
			splay::add(splay::root,Lnum,0,i + 1);
			node[nm] = splay::tot;
			splay::splay(splay::tot);
		}
		
		//if(i % 100000 == 0)
		//	fprintf(stderr,"%d %d %d\n",i,clock(),op);
	}
	
	return 0;
}