#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <map>
#include <hash_map.h>
#define N 100001
#define maxh 2000003
using namespace std;


/*
struct nod
{
    int x, y;
    int v;
    nod *next;
};

nod *aib[maxh];

inline void add(int x, int y)
{
    int h=(x*13+y)%maxh;

    nod *p;

    for(p=aib[h]; p ; p=p->next)
	if(p->x == x && p->y == y)
	{
	    ++p->v;
	    return ;
	}

    p=new nod;
    p->x=x;
    p->y=y;
    p->v=1;
    p->next=aib[h];
    aib[h]=p;
}
*/

struct nod
{
    int v,p;
    int aux;
    nod *l, *r;
    
};

typedef nod* tree;

tree aib[N], nil;

void init()
{
    nil=new nod;
    nil->l=nil->r=0;
    nil->v=nil->p=-0x3f3f3f3f;
    nil->aux=0;
    for(int i=0; i < N; ++i) aib[i]=nil;

}

inline void rotleft(tree &n)
{
    tree t=n->l;
    n->l=t->r;
    t->r=n;
    n=t;
}

inline void rotright(tree &n)
{
    tree t=n->r;
    n->r=t->l;
    t->l=n;
    n=t;
}


inline void insert(tree &n, int v)
{
    if(n == nil) 
    {
	n=new nod;
	n->l=n->r=nil;
	n->v=v;
	n->aux=1;
//	n->p=rand();
	return;
    }

    if(v == n->v) ++n->aux;

    if(v < n->v)
    {
	insert(n->l, v);
//	if(n->l->p > n->p) rotleft(n);
    }

    if(v > n->v) 
    {
	insert(n->r, v);
//	if(n->r->p > n->p) rotright(n);
    }

}


int n;

inline void update(int x, int y)
{
    int i, j;
    for(i=x; i <= n; i += i & -i)
	for(j=y; j <= n; j += j & -j)
	    insert(aib[i], j);
    //    add(i, j);
	   // ++aib[i][j];
}

int main()
{
    srand(666);

    init();
    n=50000;

    int p, q,i;

    for(i=1;i <= n; ++i)
    {
	p=rand()%n+1;
	q=rand()%n+1;

	update(p,q);
    }

    return 0;
}