P3521 [POI2011] ROT-Tree Rotations
线段树合并
首先左右子树交换只会改变「跨过左右子树的逆序对」数量,对其他逆序对不会有任何影响,所以我们选择对每个结点的左右子树求解,判断是否交换。
考虑对于每个节点建一个权值线段树,那么贡献就可以在 merge
操作中求解,原因是在权值线段树上二分,可以计算跨过 \(mid\) 的逆序对,然后继续递归求解,这部分类似归并排序。
知道了交换与不交换的贡献,加最小值即可。
复杂度 \(O(n\log n)\)。
在 merge
操作中计算贡献是很重要的做法,要熟练。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const int N = 2e5 + 10;
i64 tot, ret1, ret2;
struct seg {
int ls, rs;
i64 sum;
} t[N * 40];
i64 n, ans;
void pushup(int u, int ls, int rs) {t[u].sum = t[ls].sum + t[rs].sum;}
int ins(int &u, int l, int r, int x) {
if(!u) u = ++tot;
if(l == r) {
t[u].sum++;
return u;
}
int mid = (l + r) >> 1;
if(x <= mid) ins(t[u].ls, l, mid, x);
else ins(t[u].rs, mid + 1, r, x);
pushup(u, t[u].ls, t[u].rs);
return u;
}
int mg(int p1, int p2, int l, int r) {
if(l == r) {
t[p1].sum += t[p2].sum;
return p1;
}
int mid = (l + r) >> 1;
ret1 += t[t[p1].rs].sum * t[t[p2].ls].sum;
ret2 += t[t[p2].rs].sum * t[t[p1].ls].sum;
if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
else if(t[p2].ls) t[p1].ls = t[p2].ls;
if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
else if(t[p2].rs) t[p1].rs = t[p2].rs;
pushup(p1, t[p1].ls, t[p1].rs);
return p1;
}
int dfs() {
int x, rt;
std::cin >> x;
if(x == 0) {
int ls = dfs();
int rs = dfs();
ret1 = ret2 = 0;
rt = mg(ls, rs, 1, n);
ans += std::min(ret1, ret2);
} else {
rt = ++tot;
ins(rt, 1, n, x);
}
return rt;
}
void Solve() {
std::cin >> n;
dfs();
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}
标签:p2,p1,rs,int,sum,POI2011,Tree,ls,ROT
From: https://www.cnblogs.com/FireRaku/p/18111600