点此看题
这道题真的考思维。
有一个常见的问题转化，求冒泡的区间长度其实等价于求每个点被冒泡的次数。那么这个次数好不好求呢？我们需要考虑分割点的含义，如果一个序列全是分割点那么它就是有序的，然后对于一个位置如果两边都是分割点那么它就在正确的位置上。
如果求出了分割点出现的时间就知道了每个点冒泡的次数，因为他取决与两边分割点出现的最大时间。时间怎么求？我们把 i i i和 i + 1 i+1 i+1的分割点放在 i i i上，位置 i i i对应的应出现值是 i i i，如果后面有比 i i i小的就必须要移到 i i i前面，他们的距离是 p o s − i pos-i pos−i，所以次数也是 p o s − i pos-i pos−i（每次冒泡都会前移），找出最大的 p o s pos pos就行了。
#include <cstdio> #include <algorithm> using namespace std; const int M = 100005; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,pos,t[M];long long ans; struct node { int v,p; bool operator < (const node &b) const { if(v==b.v) return p<b.p; return v<b.v; } }a[M]; signed main() { n=read(); for(int i=1;i<=n;i++) a[i]=node{read(),i}; sort(a+1,a+1+n); for(int i=1;i<=n;i++) { pos=max(pos,a[i].p); t[i]=max(1,pos-i); } for(int i=1;i<=n;i++) ans+=max(t[i],t[i-1]); printf("%lld\n",ans); }