显然的线段树合并。
注意到交换左右子树只会影响当前结点的贡献，而其祖先并未受到影响。
考虑合并左右儿子的线段树时的贡献。
考虑线段树上分治 \([l,r]\) 区间，即计算跨过 \(mid = \lfloor \dfrac {l + r}2 \rfloor\) 的贡献数。
如果不交换，就是左边儿子 \([mid + 1,r]\) 内的点数乘上右边儿子 \([l,mid]\) 内的点数；
如果交换了，就是左边儿子 \([l,mid]\) 内的点数乘上右边儿子 \([mid + 1,r]\) 内的点数。
发现这个可以在线段树合并时同时执行，毕竟本质是基于线段树结构的算法。
于是这题就做完了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
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);
}