P3605 [USACO17JAN]Promotion Counting P

前言

【题目传送门】
小清新题目，很放松身心。
用时：\(20min\)

题解

树状数组

逆序对先想到树状数组。
大概想一想，发现从子树向父亲回溯的过程也满足逆序对的加入顺序关系。
再想想，发现不同子树内的点这样统计会出错，因为每个点只和子树内的点产生的逆序对有关。
也不难解决，进入这个点之前算一遍逆序对，走完子树后算一遍逆序对，两次的差值就是子树内的贡献啦。
代码也很小清新。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FCC fclose(stdin),fclose(stdout)
const int INF = 0x3f3f3f3f,N = 1e5+10;
inline ll read()
{
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9')) ch=c,c=getchar();
	while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
int n,a[N],p[N],tot;
int head[N],ecnt=-1;
int ans[N];
void init_edge(){memset(head,-1,sizeof(head)),ecnt=-1;}
struct edge
{
	int nxt,to;
}e[N<<1];
inline void add_edge(int x,int y)
{
	e[++ecnt]=(edge){head[x],y};
	head[x]=ecnt;
}
struct BIT
{
	int c[N];
	inline void update(int x,int v){for(int i=x;i<=tot;i+=i&-i)	c[i]+=v;}
	inline int sum(int x)
	{
		int ret=0;
		for(int i=x;i;i-=i&-i) ret+=c[i];
		return ret;
	}
	inline int query(int l,int r){return sum(r)-sum(l-1);}
}tr;
void discrete()
{
	sort(p+1,p+n+1);
	tot=unique(p+1,p+n+1)-p-1;
	for(int i=1;i<=n;i++)		
		a[i]=lower_bound(p+1,p+tot+1,a[i])-p;
	return;
}
void dfs(int u,int fa)
{
	int pre=tr.query(a[u]+1,tot);
	for(int i=head[u];~i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		tr.update(a[v],1);
	}
	int now=tr.query(a[u]+1,tot);
	ans[u]=now-pre;
}
int main()
{
	init_edge();
	n=read();
	for(int i=1;i<=n;i++) a[i]=p[i]=read();	
	discrete();
	for(int i=2;i<=n;i++)		
	{
		int u=read();
		add_edge(u,i),add_edge(i,u);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);  
	return 0;
}

线段树合并

明显也可以做，甚至看起来比模板还简单。
仍然对每一个点开一颗权值线段树，回溯的时候合并信息即可。
等下再贴代码。

树上启发式合并

显然也可做。
加深一下对书上启发式合并的理解吧，重申一下概念：
对于每一个节点 \(u\) 计算所有子树 \(v\) 内的贡献。但是为了防止不同的 \(v\) 子树之间互相干扰，所以每次走完一个 \(v\) 就要把他的贡献清除。但是当走到最后一个 \(v\) 时，它后面没有兄弟了，就不需要清除贡献，可以直接传递给父亲 \(u\)，这个最后的 \(v\) 就是 \(hson_u\)（即重儿子）。