思路就很难想+代码实现也很麻烦，知道算法后，已经写的很繁琐而且花了很长时间，200+，好久没写过这么长的代码了。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 100101
struct node
{
int l,r;
} tree[maxn];
struct nodez
{
int u,v,next;
} edge[];
int w[maxn];
int n;
int pl[maxn];
int pr[maxn];
int que[maxn];
int qu[maxn],qv[maxn];
int o[maxn];
int ww[maxn],num;
int ans1[maxn],ans2[maxn];
int tot;
int first[];
void CL()
{
tot = ;
memset(o,,sizeof(o));
memset(first,-,sizeof(first));
memset(pl,,sizeof(pl));
memset(pr,,sizeof(pr));
}
int lowbit(int t)
{
return t&(-t);
}
void insert1(int t,int d)
{
while(t <= n)
{
pl[t] += d;
t += lowbit(t);
}
}
void insert2(int t,int d)
{
while(t <= n)
{
pr[t] += d;
t += lowbit(t);
}
}
int getsum1(int t)
{
int sum = ;
while(t)
{
sum += pl[t];
t -= lowbit(t);
}
return sum;
}
int getsum2(int t)
{
int sum = ;
while(t)
{
sum += pr[t];
t -= lowbit(t);
}
return sum;
}
int bin(int x)
{
int str,end,mid;
str = ;
end = num;
while(str < end)
{
mid = (str+end)/;
if(w[mid] < x)
str = mid + ;
else
end = mid;
}
return str;
}
void add(int u,int v)
{
edge[tot].u = u;
edge[tot].v = v;
edge[tot].next = first[u];
first[u] = tot ++;
}
void dfs(int x)
{
int sp,s1,s2,s3,s4,s5,s6,i,v;
if(o[x])
{
for(i = first[x]; i != -; i = edge[i].next)
{
v = edge[i].v;
if(x == )
{
ans1[v] = ;
ans2[v] = ;
}
else
{
if(qv[v] > w[num])
{
s1 = s2 = getsum1(n);
s5 = ;
s3 = s4 = getsum2(n);
s6 = ;
sp = n;
}
else if(qv[v] < w[])
{
s1 = s2 = s3 = s4 = ;
s5 = getsum1(n);
s6 = getsum2(n);
sp = n;
}
else
{
sp = bin(qv[v]);
s1 = getsum1(sp-);
s2 = getsum1(sp);
s3 = getsum2(sp-);
s4 = getsum2(sp);
s5 = getsum1(n) - s1;
s6 = getsum2(n) - s3;
}
if(w[sp] == qv[v]&&s2 - s1 > )
{
ans1[v] = -;
ans2[v] = ;
}
else if(w[sp] == qv[v]&&s4 - s3 > )
{
ans1[v] = -;
ans2[v] = ;
}
else
{
ans1[v] = s3;
ans2[v] = s3* + s6 + s1* + s5;
}
}
}
}
if(tree[x].l != -)
{
int nu;
nu = bin(ww[x]);
insert1(nu,);
dfs(tree[x].l);
insert1(nu,-);
insert2(nu,);
dfs(tree[x].r);
insert2(nu,-);
}
return ;
}
int main()
{
int i,m,t,fa,ls,rs;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
CL();
for(i = ; i <= n; i ++)
{
scanf("%d",&w[i]);
ww[i] = w[i];
}
for(i = ; i <= n; i ++)
{
tree[i].l = tree[i].r = -;
}
sort(w+,w+n+);
num = ;
for(i = ; i <= n; i ++)
{
if(w[num] != w[i])
w[++num] = w[i];
}
scanf("%d",&m);
for(i = ; i < m; i ++)
{
scanf("%d%d%d",&fa,&ls,&rs);
tree[fa].l = ls;
tree[fa].r = rs;
}
scanf("%d",&m);
for(i = ; i <= m; i ++)
{
scanf("%d%d",&qu[i],&qv[i]);
add(qu[i],i);
o[qu[i]] = ;
}
dfs();
for(i = ; i <= m; i ++)
{
if(ans1[i] == -)
printf("0\n");
else
printf("%d %d\n",ans1[i],ans2[i]);
}
}
return ;
}