传送门 to luogu
好题啊……刚了一个上午无果。中午睡觉又想了一个小时。然后下午来操作了一个小时。最终搞定。
这个分割点到底啥子意思嘛？就是两边分别有序的时候，整个数组就有序了。
所以我们发现 分割点屁用没有。不按照分割点将数组割开，直接在原数组上进行更多的几轮冒泡，得到的结果和递归版是一样的。因为 分割点两边的元素不可能交换。
但是一旦区间划分至大小为 1 1 1 ，事情就不一样了，它不再提供 w o r k c o u n t e r \tt work\; counter workcounter 的贡献了。在被割成单个元素之前，每冒泡一次，就会为 w o r k c o u n t e r \tt work\; counter workcounter 提供 1 1 1 的贡献。
所以问题变成了，什么时候被划分成了单个元素。而划分成单个元素的意义就是，走到了正确的位置上。
我们考虑第 x x x 个数，也就是 a x a_x ax ，需要被冒泡几次。分三种大小关系讨论。
比 a x a_x ax 小的，如果在右边，需要跨越。设其为 a y a_y ay 。若 [ 1 , y ] [1,y] [1,y] 中 x x x 是第 k k k 大，则需要 k k k 次。这是因为，这 k k k 个数都会 “跨越” y y y 一次。是否包含端点 y y y 无所谓。
显然只需要最右边那一个 y y y 即可，它的约束最强。
比 a x a_x ax 大的，如果在左边，需要等待。若 [ 1 , x ] [1,x] [1,x] 中 x x x 是第 k k k 大，则需要等待 k − 1 k-1 k−1 轮。说白了就是 x x x 作为逆序对的后一个的数量。因为这 k − 1 k-1 k−1 个严格大于 x x x 的数会跨越它。
与 a x a_x ax 相等的呢？可以在离散化的时候去掉，因为冒泡是稳定的。这些都可以用树状数组解决。复杂度 O ( n log n ) \mathcal O(n\log n) O(nlogn) 。
如果你的实现想偷懒，你还可以把前两种情况合在一起。
温馨提示：第一轮要手动处理，因为第一轮就走到了正确位置也没用，仍然会产生贡献。
或者有更简单的方法，就是认为每个点至少要用 1 1 1 轮走到正确位置。我就是用的这招。
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int_; inline int readint(){ int a = 0; char c = getchar(), f = 1; for(; c<'0'||c>'9'; c=getchar()) if(c == '-') f = -f; for(; '0'<=c&&c<='9'; c=getchar()) a = (a<<3)+(a<<1)+(c^48); return a*f; } inline void writeint(int x){ if(x > 9) writeint(x/10); putchar((x%10)^48); } inline int qkpow(int_ b,int q,int m){ int ans = 1; for(; q; q>>=1,b=b*b%m) if(q&1) ans = ans*b%m; return ans; } const int MaxN = 100005; int a[MaxN], b[MaxN]; int cnt[MaxN]; // b[x] 的使用次数 int id[MaxN]; // a[id[x]] = x int ans[MaxN]; int bit[MaxN]; // 树状数组 void modify(int id,int n){ for(int i=id; i<=n; i+=(i&-i)) ++ bit[i]; } int query(int id){ int res = 0; for(int i=id; i; i-=(i&-i)) res += bit[i]; return res; } void clear(int n){ for(int i=1; i<=n; ++i) bit[i] = 0; } int main(){ int n = readint(); for(int i=1; i<=n; ++i){ a[i] = readint(); b[i] = a[i]; } if(n == 1){ // 小心！ puts("0"); return 0; } sort(b+1,b+n+1); for(int i=1; i<=n; ++i){ int x = lower_bound (b+1,b+n+1,a[i])-b; a[i] = x+cnt[x]; ++ cnt[x]; // 避免相同 id[a[i]] = i; } int_ res = 0; clear(n); /* 求后面的要怎样才会被征服 */ ; for(int i=1,x,y=0; i<=n; ++i){ x = id[i]; // i 的所在地 while(y < x) modify(a[++ y],n); res += max(y-query(i)+(y != x),1); } printf("%lld\n",res); return 0; }