题意
给一棵点带权的树，对于每个点，求其子树中有多少个点的权值 大/小/等于它(,(nleq 200000))
解法1
看到数据范围没多想就写了个树上启发式合并，太裸了。。。
维护一棵值域线段树，先跑轻儿子再跑重儿子，删轻儿子不删重儿子，自底向上求解即可，时间复杂度为(O(nlog^2n))
Code
#include<bits/stdc++.h>
#define N 200005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,a[N],b[N],len;
int size[N],son[N];
int A[N],B[N],C[N];
int sum[N<<2];
struct Edge
{
int next,to;
}edge[N<<1];int head[N],cnt=1;
void add_edge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
void modify(int rt,int l,int r,int x,int val)
{
if(l==r) return (void)(sum[rt]+=val);
int mid=(l+r)>>1;
if(x<=mid) modify(rt<<1,l,mid,x,val);
else modify(rt<<1|1,mid+1,r,x,val);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int rt,int l,int r,int x,int y)
{
if(x>y) return 0;
if(x<=l&&r<=y) return sum[rt];
int mid=(l+r)>>1;
int ret=0;
if(x<=mid) ret+=query(rt<<1,l,mid,x,y);
if(y>mid) ret+=query(rt<<1|1,mid+1,r,x,y);
return ret;
}
void DFS(int rt,int fa)
{
size[rt]=1;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
DFS(v,rt);
size[rt]+=size[v];
if(size[v]>size[son[rt]]) son[rt]=v;
}
}
void clr(int rt,int fa,int val)
{
modify(1,1,len,a[rt],val);
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
clr(v,rt,val);
}
}
void dfs(int rt,int fa)
{
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa || v==son[rt]) continue;
dfs(v,rt);
clr(v,rt,-1);
}
if(son[rt]) dfs(son[rt],rt);
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa || v==son[rt]) continue;
clr(v,rt,1);
}
A[rt]=query(1,1,len,1,a[rt]-1);
B[rt]=query(1,1,len,a[rt],a[rt]);
C[rt]=query(1,1,len,a[rt]+1,len);
modify(1,1,len,a[rt],1);
}
int main()
{
freopen("ginkgo.in","r",stdin);
freopen("ginkgo.out","w",stdout);
read(n);
for(int i=2;i<=n;++i)
{
int x; read(x);
add_edge(x,i);
add_edge(i,x);
}
for(int i=1;i<=n;++i) read(a[i]),b[++len]=a[i];
sort(b+1,b+len+1); len=unique(b+1,b+len+1)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
DFS(1,0);
dfs(1,0);
for(int i=1;i<=n;++i) printf("%d %d %d
",A[i],B[i],C[i]);
return 0;
}
解法2
只考虑怎么求小于的情况（大于的情况反过来求，等于的情况直接全集-小于-大于即可）
用dfs序将树拍成序列，对权值从小到大排序，对一个点查询子树就是查询一个区间的权值，然后再将它加入这个序列中，用个树状数组即可
时间复杂度(O(nlogn))，代码很简单就不贴了（其实是没写）
本题维护值域和维护序列皆可