binarysearch_example_spoj_orderset.cpp

#include"segment_tree.cpp"
#include"map"
#include"algorithm"
#include"stdio.h"
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
struct query{char op[2]; int x;};
struct node{
  int num_active_leaves;
	void merge(node& a, node& b){
		num_active_leaves=a.num_active_leaves+b.num_active_leaves;
	}
	bool operator<(const node& n)const{
		return num_active_leaves<n.num_active_leaves;
	}
};
void del(node& n){
	n.num_active_leaves=0;
}
void ins(node& n){
	n.num_active_leaves=1;
}

int main(){
	int ct;
	scanf("%d",&ct);
	query q[ct];

	int nums[ct];
	REP(i,ct)
		scanf("%s%d",q[i].op,&q[i].x),
		nums[i]=q[i].x;
	map<int,int> m;
	sort(nums,nums+ct);
	REP(i,ct)m[nums[i]]=i;

	node identity;
	node array[ct];
	identity.num_active_leaves=0;
	REP(i,ct)
		array[i]=identity;
	segtree<node> s;
	s.init(ct,array,identity);
	
	REP(i,ct){
		int k=q[i].x;
		q[i].x=m[q[i].x];
		switch(q[i].op[0]){
			case 'I':
				s.update<&ins>(q[i].x);
				break;
			case 'D':
				s.update<&del>(q[i].x);
				break;
			case 'C':
				if(q[i].x==0)printf("0\n");
				else printf("%d\n",s.query(0,q[i].x-1).num_active_leaves);
				break;
			case 'K':
				if(k<=0||s.query(0,100000000).num_active_leaves<k)
					printf("invalid\n");
				else{
					node n;
					n.num_active_leaves=k;
					int ans=s.binary_search(n);
					printf("%d\n",nums[ans+1]);
				}
		}
	}
}