Chika and Reverse Pairs on Tree【17th UESTC電子科技大學校賽 I題】

  題目問的就是對于每個節點，它的子節點中有多少對是我們所要找的節點對，我們要找的節點對得滿足這樣的條件，a[祖先] > a[u]，不一定是父節點的說，可以是祖父級别。

  我們可以這樣推，從葉子節點往上，我們找到每個節點的權值，先去用dp[]記錄以該節點為根的符合條件的節點的個數，然後我們再向下，找到它下面的所有節點的比他小的節點個數（嚴格小于），用到線段樹合并的思維。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, a[maxN], lsan[maxN], diff, head[maxN], cnt, root[maxN], tree[maxN * 40], lc[maxN * 40], rc[maxN * 40], tot;
ll dp[maxN];    //這個會被卡掉，要開long long
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void pushup(int rt) { tree[rt] = tree[lc[rt]] + tree[rc[rt]]; }
inline void Merge(int p1, int p2, int l, int r)
{
    if(l == r)
    {
        tree[p1] += tree[p2];
        return;
    }
    int mid = HalF;
    if(lc[p1] && lc[p2]) Merge(lc[p1], lc[p2], l, mid);
    else if(lc[p2]) lc[p1] = lc[p2];
    if(rc[p1] && rc[p2]) Merge(rc[p1], rc[p2], mid + 1, r);
    else if(rc[p2]) rc[p1] = rc[p2];
    pushup(p1);
}
inline void insert(int &rt, int l, int r, int pos)
{
    if(!rt) rt = ++tot;
    tree[rt]++;
    if(l == r) return;
    int mid = HalF;
    if(pos <= mid) insert(lc[rt], l, mid, pos);
    else insert(rc[rt], mid + 1, r, pos);
}
int query(int rt, int l, int r, int ql, int qr)
{
    if(ql <= l && qr >= r) return tree[rt];
    int mid = HalF;
    if(qr <= mid) return query(lc[rt], l, mid, ql, qr);
    else if(ql > mid) return query(rc[rt], mid + 1, r, ql, qr);
    else return query(lc[rt], l, mid, ql, qr) + query(rc[rt], mid + 1, r, ql, qr);
}
void dfs(int u)
{
    dp[u] = 0;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        dfs(v);
        dp[u] += dp[v];
        Merge(root[u], root[v], 1, diff);
    }
    int tall = (int)(lower_bound(lsan + 1, lsan + diff + 1, a[u]) - lsan);
    insert(root[u], 1, diff, tall);
    if(tall > 1) dp[u] += query(root[u], 1, diff, 1, tall - 1);
}
inline void init()
{
    cnt = 0;    tot = N;
    memset(head, -1, sizeof(head));
    memset(lc, 0, sizeof(lc));
    memset(rc, 0, sizeof(rc));
    memset(tree, 0, sizeof(tree));
}
int main()
{
    scanf("%d", &N);
    init();
    for(int i=1; i<=N; i++) { scanf("%d", &a[i]); lsan[i] = a[i]; root[i] = i; }
    for(int i=2, fa; i<=N; i++)
    {
        scanf("%d", &fa);
        addEddge(fa, i);
    }
    sort(lsan + 1, lsan + N + 1);
    diff = (int)( unique(lsan + 1, lsan + N + 1) - lsan - 1 );
    dfs(1);
    for(int i=1; i<=N; i++) printf("%lld\n", dp[i]);
    return 0;
}