欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

程序员文章站 2022-05-03 18:34:18
题意 "题目链接" Sol 线段树合并~~为什么我会在这个时候学这种东西~~ 就是暴力合并两棵线段树(必须动态开节点),遇到空节点就返回 可以证明,对于$m$个仅有一个元素,权值范围在$[1, n]$的线段树合并的复杂度为$mlogn$ 对于此题来说,显然子树内与子树外互不影响,因此暴力判断一下翻转 ......

题意

题目链接

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;
}