c/c++语言开发共享BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

题意

题目链接

sol

线段树合并为什么我会在这个时候学这种东西

就是暴力合并两棵线段树(必须动态开节点)，遇到空节点就返回

可以证明，对于(m)个仅有一个元素，权值范围在([1, n])的线段树合并的复杂度为(mlogn)

对于此题来说，显然子树内与子树外互不影响，因此暴力判断一下翻转之后会不会变优就行了

#include<bits/stdc++.h> #define ll long long  using namespace std; const int maxn = 1e7 + 10; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, val[maxn], ls[maxn], rs[maxn], tot; ll ans, c1, c2; int newtree(int l, int r, int x) {     val[++tot] = 1;     if(l == r) return tot;     int mid = l + r >> 1, now = tot;     if(x <= mid) ls[now] = newtree(l, mid, x);     else rs[now] = newtree(mid + 1, r, x);     return now; } int merge(int l, int r, int x, int y) {     if(!x || !y) return x + y;     if(l == r) {val[++tot] = val[x] + val[y]; return tot;}     c1 += 1ll * val[rs[x]] * val[ls[y]], c2 += 1ll * val[ls[x]] * val[rs[y]];     int mid = l + r >> 1, now = ++tot;     ls[now] = merge(l, mid, ls[x], ls[y]);     rs[now] = merge(mid + 1, r, rs[x], rs[y]);     val[now] = val[x] + val[y];     return now; } int dfs() {     int v = read();     if(v) return newtree(1, n, v);     int now = merge(1, n, dfs(), dfs());     ans += min(c1, c2); c1 = c2 = 0;     return now; } int main() {     n = read();     dfs();     cout << ans;     return 0; }