题解 P3521 【[POI2011]ROT-Tree Rotations】

· · 题解

【Analysis】

发现交换两个子树对其他的逆序不影响，只对跨两颗树的逆序对有影响，于是就有一个贪心；

1.权值线段树合并

从底至上，依次合并线段树，合并的时候可以顺便算一下交换和不交换产生的逆序对数，最后取min，时间复杂度O(nlog_2n)常数较大的log_2

2.Dsu on Tree

对于跨子树的逆序对暴力算就好了，可以用树状数组；时间复杂度O(nlog_2^2n)常数较小的log_2^2

【Code1】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

inline int read()
{
    int res = 0; bool f = 0; char c = getchar();
    while ((c<'0')|(c>'9')) f ^= !(c^'-'), c = getchar();
    while ((c>='0')&(c<='9')) res = (res<<1)+(res<<3)+(c^'0'),c = getchar();
    return f ? -res : res;
}

typedef long long int64;

const int MaxN = 3e5 + 11;

struct Tree
{
    int ls, rs, val;
} T[MaxN * 55];

int n, t, f;

int64 ans, ans1, ans2;

bool Is[MaxN];

inline void Mo(int& o, int v, int l = 1, int r = n)
{
    T[(!o) ? (o = ++t) : o].val ++;
    if (l == r) return ;
    int mid = l + r >> 1;
    v <= mid ? Mo(T[o].ls, v, l, mid) : Mo(T[o].rs, v, mid + 1, r);
}

inline void Merge(int &u, int v)
{
    if (!u || !v) u = u | v;
    else
    {
        T[u].val += T[v].val, ans1 += (int64)T[T[u].rs].val * T[T[v].ls].val,
        ans2 += (int64)T[T[u].ls].val * T[T[v].rs].val,
        Merge(T[u].ls, T[v].ls), Merge(T[u].rs, T[v].rs);
    }
}

void Find(int& u)
{
    int x = read(), ls, rs; u = 0;
    if (!x)
    {
        Find(ls), Find(rs); ans1 = ans2 = 0;
        Merge(ls, rs), u = ls, ans += ans1 < ans2 ? ans1 : ans2;
    } else Mo(u, x);
}

int main(void) { n = read(), Find(f = 0), printf("%lld\n", ans); return 0; }

【Code2】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

inline char gc()
{
    static char s[1<<20|1]={0},*p1=s,*p2=s;
    return (p1==p2)&&(p2=(p1=s)+fread(s,1,1<<20,stdin),p1==p2)?EOF:*(p1++);
}

inline int read()
{
    int res = 0; bool f = 0; char c = gc();
    while ((c<'0')|(c>'9')) f ^= !(c^'-'), c = gc();
    while ((c>='0')&(c<='9')) res = (res<<1)+(res<<3)+(c^'0'),c = gc();
    return f ? -res : res;
}

typedef long long int64;

const int MaxN = 4e5 + 11;

int T[MaxN>>1], Size[MaxN], Hs[MaxN], L[MaxN], R[MaxN], Num[MaxN], Dfn[MaxN];

int n, t, son;

int64 ans, ans1, ans2;

inline void Mo(int p, int v) { for (;p <= n;) T[p] += v, p += p & -p; }

inline int Qu(int p) { int v = 0; for (;p;) v += T[p], p -= p & -p; return v; }

inline void Input(int id)
{
    int x = read();
    if (!x)
    {
        Dfn[id] = ++t, Input(L[id] = t + 1), Input(R[id] = t + 1),
        Hs[id] = (Size[L[id]] >= Size[R[id]]) ? L[id] : R[id];
        Size[id] = Size[L[id]] + Size[R[id]] + 1;
    } else Num[id] = x, Size[id] = 1, Dfn[id] = ++t, Hs[id] = -1;
}

inline void Add(int u)
{
    int v = Qu(n); ans1 = ans2 = 0;
    for (int i = Dfn[u];i < Dfn[u] + Size[u]; ++i) if (Num[i])
    {
        int g = Qu(Num[i]);
        ans1 += g, ans2 += v - g;
    } for (int i = Dfn[u];i < Dfn[u] + Size[u]; ++i) if (Num[i]) Mo(Num[i], 1);
}

inline void Del(int u) { for (int i = Dfn[u];i < Dfn[u] + Size[u]; ++i) if (Num[i]) Mo(Num[i], -1); }

inline void Solve(int u, int is)
{   
    if (!~Hs[u]) { if (is) Mo(Num[u], 1); return ; }

    if (Hs[u] != L[u])
    {
        Solve(L[u], 0), Solve(R[u], 1), son = R[u], Add(L[u]), ans += (ans1 < ans2) ? ans1 : ans2;
        if (!is) Del(u);
    }
    else
    {
        Solve(R[u], 0), Solve(L[u], 1), son = L[u], Add(R[u]), ans += (ans1 < ans2) ? ans1 : ans2;
        if (!is) Del(u);
    } 
}

int main(void)
{
    n = read();
    Input(1);
    Solve(1, 1);
    printf("%lld\n", ans);
   return 0;
}