# 神奇的操作——线段树合并（例题: BZOJ2212）

2018/03/06 18:41

## 什么是线段树合并？

``````tree *merge(int l, int r, tree *A, tree *B){
if(A == NULL) return B;
if(B == NULL) return A;
if(l == r) return new tree(NULL, NULL, A -> data + B -> data);
int mid = (l + r) >> 1;
return new tree(merge(l, mid, A -> ls, B -> ls), merge(mid + 1, r, A -> rs, B -> rs), A -> data + B -> data);
}
``````

（上面的代码瞎写的……发现自己不会LaTeX写伪代码，于是瞎写了个“不伪的代码”，没编译过，凑付看 ><）

``````#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}

const int N = 10000005;
int n, tmp, ls[N], rs[N], data[N], tot;
ll ans, res1, res2;

int newtree(int l, int r, int x){
data[++tot] = 1;
int mid = (l + r) >> 1, node = tot;
if(x <= mid) ls[node] = newtree(l, mid, x);
else rs[node] = newtree(mid + 1, r, x);
return node;
}
int merge(int l, int r, int u, int v){
if(!u || !v) return u + v;
if(l == r) return data[++tot] = data[u] + data[v], tot;
int mid = (l + r) >> 1, node = ++tot;
res1 += (ll)data[rs[u]] * data[ls[v]], res2 += (ll)data[ls[u]] * data[rs[v]];
ls[node] = merge(l, mid, ls[u], ls[v]);
rs[node] = merge(mid + 1, r, rs[u], rs[v]);
data[node] = data[ls[node]] + data[rs[node]];
return node;
}
int dfs(){
if(tmp) return newtree(1, n, tmp);
int node = merge(1, n, dfs(), dfs());
ans += min(res1, res2);
res1 = res2 = 0;
return node;
}

int main(){
dfs();
write(ans), enter;
return 0;
}
``````

0
0 收藏

0 评论
0 收藏
0