LuoguP3521 [POI2011]ROT-Tree Rotations
题目
题解
考虑对于一个子树有三种可能的逆序对:
1.在左子树中
2.在右子树中
3.跨过左右子树
显然对于交换左右子树的操作,只有第3种会受影响,且只有当前这个节点有关
所以对每个子树开个权值线段树即可,可以用线段树合并实现
#include<bits/stdc++.h> using namespace std; #define ll long long #define re register inline ll read() { ll f = 1,x = 0; char ch; do { ch = getchar(); if(ch == '-') f = -1; }while(ch<'0'||ch>'9'); do { x = (x<<3) + (x<<1) + ch - '0'; ch = getchar(); }while(ch>='0'&&ch<='9'); return f*x; } const int MAXN = 4e5 + 10; int n; int root = 0; ll ans1,ans2,ans; int lson[MAXN*40],rson[MAXN*40]; int sum[MAXN*40]; int cnt; inline void update(int &rt,int l,int r,int k) { if(!rt) rt = ++cnt; if(l == r) { sum[rt] += 1; return; } int mid = (l+r)>>1; sum[rt]++; if(k <= mid) update(lson[rt],l,mid,k); else update(rson[rt],mid+1,r,k); return; } inline void merge(int &l,int r) { if(!l||!r) { l = l + r; return; } ans1 += (long long)sum[lson[l]] * (long long)sum[rson[r]]; ans2 += (long long)sum[rson[l]] * (long long)sum[lson[r]]; sum[l] += sum[r]; merge(lson[l],lson[r]); merge(rson[l],rson[r]); return; } inline void dfs(int &rt) { int val = read(); int lc = 0,rc = 0; if(!val) { dfs(lc);dfs(rc); rt = lc;ans1=ans2=0; merge(rt,rc); ans += min(ans1,ans2); } else update(rt,1,n,val); } int main() { n = read(); dfs(root); cout << ans << endl; }