题目貌似有锅..
它说输出最少旋转次数，然而应该是最少逆序对数...
考虑一个把子树合并的过程，在子树合并时计算左右子树产生的逆序对数
这样一直合并最后就是答案
所以可以对每个子树建一个权值线段树
然后把权值线段树合并
合并时计算逆序对只要计算跨 mid 的逆序对
如果翻转也只要计算跨 mid 的数，一样处理
然后递归下去继续合并
可以发现我们交换左右子树不会对更上面的逆序对数产生影响
只要保证每次都取最小值，那么最终也就是最小值
所以统计答案直接取翻转和不翻转的较小值
注意要动态开点，空间卡一下就过了
读入有点坑
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n; struct node { int sz,lc,rc; node () { sz=lc=rc=0; } }t[N*25]; int cnt; int pos; ll res1,res2,ans; void ins(int &o,int l,int r)//往权值线段树中插入pos { if(!o) o=++cnt; t[o].sz++; if(l==r) return; int mid=l+r>>1; if(pos<=mid) ins(t[o].lc,l,mid); else ins(t[o].rc,mid+1,r); } void merge(int &o1,int o2)//合并两颗权值线段树，（把o2合入o1） { if(!o1||!o2) { o1=o1+o2; return; } res1+=1ll*t[t[o1].rc].sz*t[t[o2].lc].sz;//计算跨mid的贡献 res2+=1ll*t[t[o1].lc].sz*t[t[o2].rc].sz;//注意乘的时候可能爆int merge(t[o1].lc,t[o2].lc); merge(t[o1].rc,t[o2].rc);//递归下去合并 t[o1].sz+=t[o2].sz;//更新线段树 } void solve(int &x)//递归读入 { int t=read(),l=0,r=0; if(!t) { solve(l),solve(r); res1=res2=0; x=l; merge(x,r);//合并 ans+=min(res1,res2);//取较小值 } else pos=t,ins(x,1,n);//初始对每个叶子建一个权值线段树 } int main() { n=read(); int x=0; solve(x); printf("%lld",ans); return 0; }