TIOJ 1305 啊嘶起啦集合 [segment tree]

poao899    6372K    417MS    G++     2.62K     2009-12-01 17:43:27                           .

離散化 + segment tree


是說是不是用兩個map來離散化頗詭異(?


//***************************

#include<stdio.h>
#include<map>
#include<algorithm>
#define MAX 300000
std::map<int,int> keyToVal;
std::map<int,int> valToKey;
struct segment{
	int  l,r,sub;
	bool inSet;
	segment *seg_l,*seg_r;
}Seg[MAX];
segment* set(int l,int r){
	static int cnt = 1;
	Seg[cnt].l=l;
	Seg[cnt].r=r;
	return Seg+cnt++;
}
bool insert(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){
		if(! p->inSet){
			p->inSet=1;
			p->sub=1;
			return true;
		}
		return false;
	}
	segment *q;
	int mid = ( l + r + 1 )/2;
	if(mid > i){
		if(p->seg_l==NULL){
			q = set(l,mid);
			p->seg_l=q;
		}
		q=p->seg_l;
	}
	else{
		if(p->seg_r==NULL){
			q = set(mid,r);
			p->seg_r=q;
		}
		q=p->seg_r;
	}
	if(insert(q,i)){
		p->sub++;
		return true;
	}
	return false;
}
bool remove(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){
		if(p->inSet){
			p->inSet=0;
			p->sub=0;
			return true;
		}
		return false;
	}
	segment *q;
	int mid = ( l + r + 1 )/2;
	if(mid > i){
		if(p->seg_l==NULL)
			return false;
		q=p->seg_l;
	}
	else{
		if(p->seg_r==NULL)
			return false;
		q=p->seg_r;
	}
	if(remove(q,i)){
		p->sub--;
		return true;
	}
	return false;
}
int ask(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){return l;}
	if(p->seg_l!=NULL){
		if(p->seg_l->sub>=i){
			return ask(p->seg_l,i);
		}
	}
	if(p->seg_r!=NULL){
		if(p->seg_l!=NULL){
			return ask(p->seg_r,i-p->seg_l->sub);
		}
		return ask(p->seg_r,i);
	}
}
void get(char &c,int &n){
	c=getchar();
	int s=1;n=0;
	char g=getchar();
	while((g<'0'||g>'9') && g!='-'){
		if(g=='\n')return;
		g=getchar();
	}
	if(g=='-')g=getchar(),s=-1;
	while(g>='0'&&g<='9'){
		n=n*10+g-48;
		g=getchar();
	}
	n*=s;
}
char com[MAX];
int num[MAX];
int comCnt,keyCnt;
int dsc[MAX];
int kCnt=1;
int main(){
	while(1){
		get(com[comCnt],num[comCnt]);
		if(com[comCnt]=='e')break;
		if(com[comCnt]!='a'){
			dsc[keyCnt]=num[comCnt];
			keyCnt++;
		}
		comCnt++;
	}
	std::sort(dsc,dsc+keyCnt);
	for(int i=0;i<keyCnt;i++){
		if(valToKey[dsc[i]]==0){
			valToKey[dsc[i]]=kCnt;
			keyToVal[kCnt]=dsc[i];
			kCnt++;
		}
	}
	Seg->sub=0;
	Seg->l=1;
	Seg->r=kCnt;
	for(int i=0;i<comCnt;i++){
		switch(com[i]){
			case'a':
				if(num[i]<=0 || num[i]>Seg->sub)
					puts("error");
				else printf("%d\n" ,keyToVal[ask(Seg,num[i])]);
				break;
			case'i':
				insert (Seg,valToKey[num[i]]);
				break;
			case'r':
				remove(Seg,valToKey[num[i]]);
				break;
		}
	}
}