刷题记录:牛客NC24048[USACO 2017 Jan P]Promotion Counting 求子树的逆序对个数

传送门:牛客

题目描述

奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训–牛是可怕的管理者！
为了方便，把奶牛从 $1\sim n$ 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。
所有的第 $i$ 头牛都有一个不同的能力指数 $p_i$，描述了她对其工作的擅长程度。如果奶牛 $i$ 是奶牛 $j$ 的祖先节点，那么我们我们把奶牛 $j$ 叫做 $i$ 的下属。
不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 $i$，请计算其下属 $j$ 的数量满足 $p_j>p_i$。

输入:
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
输出:
2
0
1
0
0

刚开始我以为是一道树链剖分的题目.然后发现这道题本质上应该是一道树上$dfs$的题目

当然树链剖分暴力解决这道题也是可以做的,对于树剖,复杂度时log级别的.可以考虑使用树剖将树形结构转化为线性结构,然后考虑维护区间逆序对个数.此时我们无法使用线段树进行维护.对于维护区间逆序对个数,我们考虑使用分块进行维护,朴素莫队可以在$N\sqrt{N}logN$解决.复杂度还是满足本题的.但是使用上述方法解决本题是在是杀鸡用牛刀,本题还是用不到那么复杂的维护方法的

对于本题来说,我们只需要计算一个节点的所有儿子的贡献即.因为父亲对儿子是没有贡献的,所以我们考虑使用$dfs$来解决这道题.使用权值树状数组(当然权值线段树也是可以的)来维护每一个权值.那么对于一个节点$u$来说,我们只需要遍历他的所有儿子节点,并且将所有权值都存入权值树状数组中,然后对于$u$节点的答案来说,就是当前比他大的节点的个数.但是这么做的话存在一个问题,因为我们的这棵BIT此时存的不只是当前结点的儿子的权值,之前遍历其他节点的时候也存了,所以此时会导致一些错误.解决此问题的方案是,在遍历该节点的儿子节点之前先减去之前所有已在节点的贡献即可.这样的话就相当于减去了其他不满足子树的贡献

本题需要进行离散化操作

---

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int tree[maxn];int n;
int lowbit(int x) {return x&(~x+1);
}
void Add(int pos,int val) {while(pos<=n) {tree[pos]+=val;pos+=lowbit(pos);}
}
int query(int pos) {int ans=0;while(pos) {ans+=tree[pos];pos-=lowbit(pos);}return ans;
}
int w[maxn];vector<int>v;int Size;
vector<int>edge[maxn];int ans[maxn];
int get_id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void dfs1(int u,int per_u) {int x=get_id(w[u]);ans[u]-=query(Size)-query(x);for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dfs1(v,u);}ans[u]+=query(Size)-query(x);Add(x,1);
}
int main() {n=read();for(int i=1;i<=n;i++) {w[i]=read();v.push_back(w[i]);}sort(v.begin(),v.end());Size=v.size();for(int i=2;i<=n;i++) {int u=read();edge[u].push_back(i);}dfs1(1,0);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}