https://www.luogu.org/problemnew/show/P4372

题意：如果数组A中A[...i]的最大值<=A[i+1…]的最小值，则称i和i+1位置之间产生了一个分隔点，然后对分隔点左右递归求解，一个区间只有一个元素就返回，最后求冒泡排序变量work_counter的值，衡量冒泡排序工作量。

思路：

与这两道题是一路的：https://blog.csdn.net/Wen_Yongqi/article/details/87886315

先把数组元素离散化，化为1~n，下面直接说的是1~n。

定义点i：i位置与i+1位置之间的分隔点，

定义t[i]:点i出现的时间，即1~i元素全部到达1~i位置的时间，即最右的本应在分隔点i左边的元素位置maxpos到点i位置的距离。如果本来1~i已经全部在位置1~i里面了，那么t[i]=1，因为冒泡排序至少要扫一遍。

对于任意元素i，i对答案ans产生贡献直到i>=左边最大值并且<=右边最小值，即i左右都产生了分隔点，即点i-1和点i都是分隔点。

所以答案就是Σmax{t[i],t[i-1]},i∈[1,n]。

为什么要取max呢？因为两边必须都是分隔点才行，比如3142，t[2]=2,t[3]=1,位置3要想作为分隔点，必须满足1~2在1~2并且4在4。或者这个例子12543，t[2]=1,t[3]=2，这个3也必须归位。

为什么只考虑1~i从右边到达左边而不是考虑1~i中>i的出去呢?因为1~i大于i的出去未必<=i的进来，而<=i的进来必定>i的出去。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+100
#define lowbit(x) (x&-x)

int n,a[maxn],r[maxn],t[maxn];
long long ans;

bool cmp(int x,int y)
{
	if(a[x]!=a[y])return a[x]<a[y];
	return x<y;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],r[i]=i;
	sort(r+1,r+1+n,cmp);
	for(int i=1;i<=n;i++)a[r[i]]=i;
	int maxpos=0;
	for(int i=1;i<=n;i++)
	{
		maxpos=max(maxpos,r[i]);
		t[i]=max(1,maxpos-i);
	}
	for(int i=1;i<=n;i++)ans+=max(t[i-1],t[i]);
	cout<<ans<<endl;
	return 0;
}