http://acm.hdu.edu.cn/showproblem.php?pid=4605
可以离线求解
把所以可能出现的 magic ball 放在一个数组里(去重)，从小到大排列
先不考虑特殊情况，对二叉树进行dfs 搜索的过程中需要维护各个magic ball到当前节点的概率
维护：根据当前节点大小 和要去左子树还是右子树的情况，可以得到magic数组中哪个段的x和y需要同时加上多少
可以用线段树维护
特殊情况：
1，根节点一定可以到达
2，到达不了的情况需要标记
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#include<queue>
#include<stdexcept>
#include<bitset>
#include<cassert>
#include<deque>
#include<numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pp;
const double eps=1e-12;
const int INF=0x3f3f3f3f;
const ll MOD=1000000007;
const int N=100010;
struct node
{
int l,r;
int fm,fn;
}tree[N*4];
int f[N];
int a[N];
int stop[N];
int qv[N],qx[N],qm[N],qn[N];
int bl[N],br[N];
int weight[N];
vector<int>vt[N];
void build(int x,int l,int r)
{
tree[x].l=l;
tree[x].r=r;
tree[x].fm=0;
tree[x].fn=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build((x<<1),l,mid);
build((x<<1)|1,mid+1,r);
}
void add(int x,int l,int r,int km,int kn)
{
if(l>r) return ;
if(tree[x].l==l&&tree[x].r==r)
{
tree[x].fm+=km;
tree[x].fn+=kn;
return ;
}
int mid=(tree[x].l+tree[x].r)>>1;
if(r<=mid)
add((x<<1),l,r,km,kn);
else if(l>mid)
add((x<<1)|1,l,r,km,kn);
else
{
add((x<<1),l,mid,km,kn);
add((x<<1)|1,mid+1,r,km,kn);
}
}
void get(int x,int k,int &m,int &n)
{
m+=tree[x].fm;n+=tree[x].fn;
if(tree[x].l==tree[x].r)
{return ;}
int mid=(tree[x].l+tree[x].r)>>1;
if(k<=mid)
get((x<<1),k,m,n);
else
get((x<<1)|1,k,m,n);
}
int bse(int l,int r,int k)
{
while(l<=r)
{
int m=(l+r)>>1;
if(a[m]<=k)
l=m+1;
else
r=m-1;
}
return r;
}
void dfs(int x,int ln)
{
for(unsigned int i=0;i<vt[x].size();++i)
{
int t=vt[x][i];
int w=bse(1,ln,qx[t]);
int m=0,n=0;
if(!stop[w])
{get(1,w,m,n);}
qm[t]=m;
qn[t]=n;
}
if(bl[x]!=0&&br[x]!=0)
{
int l=bse(1,ln,weight[x]);
int ll=l,rr=l+1;
if(a[l]==weight[x])
stop[l]++;
add(1,1,ll,0,1);
add(1,rr,ln,0,3);
dfs(bl[x],ln);
add(1,1,ll,0,-1);
add(1,rr,ln,0,-3);
add(1,1,ll,0,1);
add(1,rr,ln,1,3);
dfs(br[x],ln);
add(1,1,ll,0,-1);
add(1,rr,ln,-1,-3);
if(a[l]==weight[x])
stop[l]--;
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("1006.in","r",stdin);
//freopen("my.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
for(int i=0;i<N;++i)
vt[i].clear();
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&weight[i]);
int m;
scanf("%d",&m);
memset(bl,0,sizeof(bl));
memset(br,0,sizeof(br));
while(m--)
{
int v,l,r;
scanf("%d %d %d",&v,&l,&r);
f[l]=v;
f[r]=v;
bl[v]=l;
br[v]=r;
}
int ln=0;
a[++ln]=0;
a[++ln]=1e9+10;
int Q;
scanf("%d",&Q);
for(int i=0;i<Q;++i)
{
scanf("%d %d",&qv[i],&qx[i]);
a[++ln]=qx[i];
if(qv[i]!=1)
{
vt[qv[i]].push_back(i);
}
}
sort(a+1,a+ln+1);
int l=0;
for(int i=1;i<=ln;++i)
if(i==1||a[i]!=a[i-1])
a[++l]=a[i];
ln=l;
build(1,1,ln);
memset(stop,0,sizeof(stop));
dfs(1,ln);
for(int i=0;i<Q;++i)
{
if(qv[i]==1)
{printf("0 0
");continue;}
if(qm[i]==0&&qn[i]==0)
printf("0
");
else
printf("%d %d
",qm[i],qn[i]);
}
}
return 0;
}