#include <cstdio>
#include <cstdlib>
#include <ctime>
#define N 100001
#define common \
	int m=(l+r)>>1, L=n<<1, R=L|1
	
	

struct nod
{
	int nr;
	nod *next[2];
	nod() { nr=0; next[0]=0; next[1]=0;};
};

typedef nod* trie;

trie R=new nod;

void insert_trie(trie T, int n)
{
	int c;
	for(int i=31; i >= 0; --i)
	{
		c=n & (1<<i);
		if(c) c=1;
		if(T->next[c] == 0)
			T->next[c]=new nod;
	
		++T->nr;
		T=T->next[c];
	}
	
	++T->nr;
}

 inline void insrt(trie &T, int n, int i)
{
	if(i < 0) return;
	int c=n & (1<<i);
	if(c) c=1;
	
	if(T->next[c] == 0) T->next[c]=new nod;
	
	++T->nr;
	insrt(T->next[c], n,i-1);
}

inline void erase(trie &T, int n, int i)
{
	if(i < 0 ) return;
	int c=n & (1 << i);
	if(c) c=1;
	
	erase(T->next[c], n, i-1);
	
	--T->nr;
	
	if(T->next[c]->nr == 0)
	{
		delete T->next[c];
		T->next[c]=0;
	}
}

inline int find(trie T, int n)
{
	int c;
	for(int i=31; i >= 0; --i)
	{
		c=n & (1<<i);
		if(c) c=1;
		
		if(T->next[c] == 0) return 0;
		T=T->next[c];
	}
	
	return 1;
}

trie H[(1<<18)+1];

inline void update(int n, int l,int r, int p, int v)
{
	if(H[n] == 0) 
			H[n]=new nod;
		
	if(l >= r)
	{
		insert_trie(H[n], v);
		return;
	}
	
	insert_trie(H[n], v);
	
	common;
	
	if(p <= m) update(L, l, m, p, v);
	else update(R, m+1, r, p, v);
	
}


trie aib[N];
int n;

inline void update(int x, int v)
{
	for(int i=x; i <= n; i += i & -i)
	{
		if(aib[i] == 0) aib[i]=new nod;
		insert_trie(aib[i], v);
	}
}


int main()
{
	
	double s=clock();
	
	n=50000;
	
	for(int i=1; i <= n; ++i) update(i, rand()); 
	//	update(1, 1, n, i, rand());
	//insert_trie(R, 12);

	
	printf("%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	return 0;
}