题面：P3605 [USACO17JAN]Promotion Counting晋升者计数
题解：这是一道万能题，树状数组 || 主席树 || 线段树合并 || 莫队套分块 || 线段树 都可以写。。记得离散化
线段树合并版：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=(1e5)+;
int N,num_edge=,edge_head[maxn],W[maxn],lsh_cnt=,num_treenode=;
int root[maxn],ans[maxn],u;
struct A_{int id,data;}A[maxn];
inline bool cmp(const A_&a,const A_&b){return a.data<b.data;}
struct Edge{int to,nx;}edge[maxn];
inline void Add_edge(int from,int to){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].to=to;
edge_head[from]=num_edge;
return;
}
struct Tree{int lc,rc,l,r,cnt;}t[maxn*];
inline void Build(int x,int l,int r,int q){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r&&l==q){
t[x].cnt=;
return;
}
if(q<=mid)Build(t[x].lc=++num_treenode,l,mid,q);
else Build(t[x].rc=++num_treenode,mid+,r,q);
t[x].cnt=t[t[x].lc].cnt+t[t[x].rc].cnt;
return;
}
inline int Merge(int u,int v){
if(!u)return v;
if(!v)return u;
int l=t[u].l,r=t[u].r;
if(l==r){
t[u].cnt+=t[v].cnt;
return u;
}
t[u].lc=Merge(t[u].lc,t[v].lc);
t[u].rc=Merge(t[u].rc,t[v].rc);
t[u].cnt=t[t[u].lc].cnt+t[t[u].rc].cnt;
return u;
}
inline void Query(int g,int x,int ql,int qr){
int l=t[x].l,r=t[x].r,mid=(l+r)>>,lc=t[x].lc,rc=t[x].rc;
if(x==)return;
if(ql<=l&&r<=qr){
ans[g]+=t[x].cnt;
return;
}
if(ql<=mid)Query(g,lc,ql,qr);
if(qr>mid) Query(g,rc,ql,qr);
return;
}
inline void Dfs(int x){
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
Dfs(y);
root[x]=Merge(root[x],root[y]);
}
if(W[x]+>lsh_cnt)ans[x]=;
else Query(x,root[x],W[x]+,lsh_cnt);
return;
}
int main(){
scanf("%d",&N);
for(int i=;i<=N;i++){
scanf("%d",&A[i].data);
A[i].id=i;
}
sort(A+,A+N+,cmp);
W[A[].id]=++lsh_cnt;
for(int i=;i<=N;i++)
if(A[i].data!=A[i-].data)W[A[i].id]=++lsh_cnt;
else W[A[i].id]=lsh_cnt;
for(int i=;i<=N;i++){
scanf("%d",&u);
Add_edge(u,i);
}
for(int i=;i<=N;i++)Build(root[i]=++num_treenode,,lsh_cnt+,W[i]);
Dfs();
for(int i=;i<=N;i++)printf("%d\n",ans[i]);
return ;
}
树状数组版：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define re register
using namespace std;
inline int rd(){
int x=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x;
}
const int maxn=1e5;
int N,P[maxn+],cnt=,num_edge=,edge_head[maxn+],F,C[maxn+];
ll ans[maxn+];
struct Edge{
int to,nx;
}edge[maxn+];
struct Node{
int x,id;
}A[maxn+];
inline bool cmp(const Node&a,const Node&b){
if(a.x<b.x)return ;
return ;
}
inline int Find(int x){
re ll ans=;
for(;x<=cnt;x+=x&(-x))ans+=C[x];
return ans;
}
inline void Update(int x){
for(;x>;x-=x&(-x))C[x]++;
return;
}
inline void Dfs(int x){
ans[x]-=Find(P[x]);
for(re int i=edge_head[x];i;i=edge[i].nx) Dfs(edge[i].to);
ans[x]+=Find(P[x]);
Update(P[x]);
return;
}
int main(){
N=rd();
for(re int i=;i<=N;i++){
A[i].x=rd();
A[i].id=i;
}
sort(A+,A+N+,cmp);
for(re int i=;i<=N;i++){
if(i==||A[i].x!=A[i-].x)cnt++;
P[A[i].id]=cnt;
}
for(re int i=;i<=N;i++){
scanf("%d",&F);
edge[++num_edge].nx=edge_head[F];
edge[num_edge].to=i;
edge_head[F]=num_edge;
}
Dfs();
for(re int i=;i<=N;i++)printf("%lld\n",ans[i]);
return ;
}
By:AlenaNuna