问题2519--树上逆序对

2519: 树上逆序对

时间限制: 1 Sec  内存限制: 256 MB
提交: 98  解决: 41
[状态] [讨论版] [提交] [命题人:]
题目描述
一天,Chika 在研究关于所谓的树上逆序对的问题,你能帮助她吗?她会给你一棵有根树,这棵树有 n 个 结点,被编号为 1~ n,1 号结点是根。每个点有一个权值,i 号结点的权值为 a[i]。如果 u 是 v 的祖先结点, 并且 a[u] > a[v],那么 (u,v) 被称作一个“** 逆序对 **”。 
Chika 会给你 m 个任务,包含两种类型: 
1 u x : 向树中添加一个新结点,其父亲为 u,权值为 x。执行完这个操作后,树的结点总数增加 1,因此该 结点的编号为 n+1(n 为添加这个点之前树中的总结点数)。 
2 u : 你需要回答如果删除以 u 为根的子树,树的剩余部分的逆序对数。任意两个类型 2 的任务之间互相 独立。
你需要完成所有任务。
输入
输入文件的第一行包含两个整数 n (1≤n≤105) 和 m (1≤m≤105),代表树中初始状态的结点总数以及 任务总数。 
第二行包含 n 个整数,第 i 个整数是 a[i] (1≤ a[i] ≤109),代表 i 号结点的权值。 
第三行包含 n−1 个整数,第 i 个整数是 i+1 号结点的父结点。 
接下来是 m 行,每一行描述了一个任务,满足以下两种格式之一: 
1 u x 
2 u 
对于每个任务,u 都满足不小于 1 且不超过该时刻树中结点的总数。对于每个类型 1 的任务,x 都满足 1≤ x ≤109。 
你可以在本题的描述中找到任务的含义。 
输出
对于每个类型2的任务,你应该输出一行,仅包含一个数字,代表你的答案。

样例输入 Copy
10 10
10 2 9 2 8 7 8 3 1 8
1 1 2 3 5 2 5 6 2
1 1 6
2 3
1 9 5
2 1
2 7
1 12 2
2 6
1 11 13
2 10
2 11
样例输出 Copy
5
0
21
11
26
26
来源/分类