BZOJ 2212.「POI2011」Tree Rotations

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

考虑合并左右儿子的线段树时的贡献。
考虑线段树上分治 [l,r][l,r] 区间,即计算跨过 mid=l+r2mid = \lfloor \dfrac {l + r}2 \rfloor 的贡献数。
如果不交换,就是左边儿子 [mid+1,r][mid + 1,r] 内的点数乘上右边儿子 [l,mid][l,mid] 内的点数;
如果交换了,就是左边儿子 [l,mid][l,mid] 内的点数乘上右边儿子 [mid+1,r][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
#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);
}