BZOJ 2212. 「POI2011」Tree Rotations

显然的线段树合并。
注意到交换左右子树只会影响当前结点的贡献，而其祖先并未受到影响。

考虑合并左右儿子的线段树时的贡献。
考虑线段树上分治区间，即计算跨过的贡献数。
如果不交换，就是左边儿子内的点数乘上右边儿子内的点数；
如果交换了，就是左边儿子内的点数乘上右边儿子内的点数。

发现这个可以在线段树合并时同时执行，毕竟本质是基于线段树结构的算法。
于是这题就做完了。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 2e5;
int n,rt;
long long ans,ans1,ans2;
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 5) + 10];
void insert(int x,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    ++seg[p].sum;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int merge(int x,int y)
{
    if(!x || !y)
        return x | y;
    seg[x].sum += seg[y].sum;
    ans1 += (long long)seg[seg[x].rs].sum * seg[seg[y].ls].sum,ans2 += (long long)seg[seg[x].ls].sum * seg[seg[y].rs].sum;
    seg[x].ls = merge(seg[x].ls,seg[y].ls),seg[x].rs = merge(seg[x].rs,seg[y].rs);
    return x;
}
void dfs(int &p)
{
    int x,ch[2] = {0};
    read(x);
    if(!x)
        dfs(ch[0]),dfs(ch[1]),ans1 = ans2 = 0,p = merge(ch[0],ch[1]),ans += min(ans1,ans2);
    else
        insert(x,p,1,n);
}
int main()
{
    read(n),dfs(rt),printf("%lld\n",ans);
}

『My guiding star.』

BZOJ 2212 「POI2011」Tree Rotations