首页 > 代码库 > bzoj2212

bzoj2212

2024-09-23 17:09:31   216人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=2212

线段树合并。。。

感觉这东西挺鬼畜的。。。不是很懂

这道题思想很简单，对于每个非叶子结点，我们要合并左右儿子的数，我们可以交换或者不交换，那么交换了其实只会自己内部有影响，对下一次合并没有影响，也就是说我们要看交换了的你需对多还是没交换的逆序对多。。。所以我们维护一个权值线段树，每次合并时左边的size就是左边有多少个数，右边的size就是右边有多少数，那么我们只要比较size[lc[x]]*size[rc[y]]和size[rc[x]]*size[lc[y]]就可以了，然后加上，比较最小值。。。记住是先更新再合并。。。

技术分享 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6000010;
int cnt, tot, n;
ll size[N], ans, ans1, ans2;
int lc[N], rc[N], v[N], root[N], child[N][2]; 
void update(int l, int r, int &x, int pos)
{
    x = ++tot; int mid = (l + r) >> 1; 
    ++size[x]; if(l == r) return;
    if(pos <= mid) update(l, mid, lc[x], pos);
    else update(mid + 1, r, rc[x], pos);
}
int merge(int x, int y)
{
    if(!x) return y;
    if(!y) return x;
    ans1 += size[lc[x]] * size[rc[y]];
    ans2 += size[rc[x]] * size[lc[y]];
    lc[x] = merge(lc[x], lc[y]);
    rc[x] = merge(rc[x], rc[y]);
    size[x] = size[lc[x]] + size[rc[x]];
    return x;
}
void Init(int u)
{
    scanf("%d", &v[u]); 
    if(!v[u]) 
    {
        child[u][0] = ++cnt; child[u][1] = ++cnt; 
        Init(child[u][0]);     Init(child[u][1]);     
    }
}
void dfs(int u)
{
    if(v[u]) return;
    dfs(child[u][0]); dfs(child[u][1]);
    ans1 = ans2 = 0;
    root[u] = merge(root[child[u][0]], root[child[u][1]]);
    ans += min(ans1, ans2); 
}
int main()
{
    scanf("%d", &n); ++cnt;
    Init(cnt); 
    for(int i = 1; i <= cnt; ++i) if(v[i]) update(1, n, root[i], v[i]);
    dfs(1);
    printf("%lld\n", ans);
    return 0;
}
View Code

 

bzoj2212


联系
我们