QHsx92 - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
int n, q;
struct sec
{
	int l, r;
};
sec merge(sec a, sec b)
{
	sec c;
	c.l = min(a.l, b.l);
	c.r = max(a.r, b.r);
	return c;
}
struct node
{
	int id, k, ls, rs;
	sec sc;
};
node a[200010];
vector <int> e[200010];
int fa[200010];
void find_lr(int x)
{
	for (auto y : e[x])
		if (y != fa[x])
			find_lr(y);
	sec now;
	if (x == 1)
		now = (sec){-2000000000, 2000000000};
	else
		now = (sec){a[x].k, a[x].k};
	for (auto y : e[x])
		if (y != fa[x])
			now = merge(now, a[y].sc);
	a[x].sc = now;
}
bool check(sec a, sec b)
{
	if (b.l <= a.l && a.r <= b.r)
		return 0;
	if (a.r < b.l)
		return 0;
	if (a.l > b.r)
		return 0;
	return 1;
}
int output = 0;
sec Wen;
void run(int x)
{
	output++;
	if (x == 0)
		return ;
	if (check(a[x].sc, Wen) == 0)
		return ;
	run(a[x].ls);
	run(a[x].rs);
}
map <pair<int, int>, int> mem;
int mapp[2010];
int main()
{
    freopen("two.in", "r", stdin);
    freopen("two.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		a[i].id = i;
		cin >> a[i].ls >> a[i].rs >> a[i].k;
		if (a[i].ls != 0)
		{
			e[i].push_back(a[i].ls);
			e[a[i].ls].push_back(i);
			fa[a[i].ls] = i;
		}
		if (a[i].rs != 0)
		{
			e[i].push_back(a[i].rs);
			e[a[i].rs].push_back(i);
			fa[a[i].rs] = i;
		}
		mapp[i] = a[i].k;
	}
	sort (mapp + 1, mapp + n + 1);
	a[0].sc = (sec){-2000000000, -2000000000};
	find_lr(1);
	int q;
	cin >> q;
	if (n <= 2000 && q <= 2000)
	{
		while (q--)
		{
			int L, R;
			cin >> L >> R;
			Wen = (sec){L, R};
			output = 0;
			run(1);
			cout << output << endl;
		}
		return 0;
	}
	while (q--)
	{
		int L, R;
		cin >> L >> R;
		Wen = (sec){L, R};
		pair <int, int> memchk;
		memchk.first = lower_bound(mapp + 1, mapp + n + 1, L) - mapp;
		memchk.second = upper_bound(mapp + 1, mapp + n + 1, R) - mapp - 1;
		if (mem.find(memchk) != mem.end())
		{
			cout << mem[memchk] << endl;
		}
		else
		{
			output = 0;
			run(1);
			cout << output << endl;
			mem[memchk] = output;
		}
		// cout << memchk.first << " " << memchk.second << endl;
	}
	return 0;
}