#include <cstdio>
#include <string>
#include <ctime>
#define maxn 1024

int H[3*maxn][3*maxn];
int N=1000,SUM=0;

inline void update2(int i, int n, int l, int r, int p)
{
	++H[i][n];
	if(l>=r) return ;
	int m=(l+r)>>1;
	if(m>p) update2(i, n<<1, l, m, p);
	else    update2(i, (n<<1)|1, m+1, r, p);
}

inline void update(int n, int l, int r, int a, int b)
{
	update2(n, 1, 1, N, b);
	if(l>=r) return ;
	int m=(l+r)>>1;
	if(m>a) update(n<<1, l, m, a, b);
	else    update((n<<1)|1, m+1, r, a, b);
}

inline int query2(int i, int n, int l, int r, int a, int b)
{
	if(a<=l && r<=b) return H[i][n];
	int m=(l+r)>>1;
	int t=0;
	if(m>=a) t+=query2(i, n<<1, l, m, a, b);
	if(m<b) t+=query2(i, (n<<1)|1, m+1, r, a, b);
	return t;
}

inline void query(int n, int l, int r, int a, int b, int c, int d)
{
	if(a<=l && r<=b) 
	{
		SUM+=query2(n, 1, 1, N, c, d);
		return ;
	}
	int m=(l+r)>>1;
	if(m>=a) query(n<<1, l, m, a, b, c, d);
	if(m<b) query((n<<1)|1, m+1, r, a, b,c, d);
}


int main()
{
	srand(time(0));
	double s=clock();
	for(int i=1;i<=100000;++i) update(1, 1, N, rand()%1000, rand()%1000);
	
	printf("%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	
	
	return 0;
}