BZOJ 5277 IQ题orz

思路：

首先我们注意到，对一个序列按分割点分开以后分别冒泡其实就相当于对整个序列进行冒泡。每一个元素都会对复杂度贡献1，除非一个元素两边的分割点都出现了。因此我们可以完全忽略快排的递归过程。只需考虑每个元素在经历几趟冒泡排序之后两边的分割点都出现了。

考虑一个分割点，不妨就是在i,i+1之间的这个分割点，他在几趟冒泡排序之后会出现呢？出现了这个分割点，说明前i小的元素都已经在前i个了，我们记前i小的元素一开始最大的下标为x，则在x-i趟冒泡之后就会把x挪到前i个位置（因为每趟冒泡一定会使x的下标-1）。也就是说i,i+1之间的分割点会在x-i趟冒泡之后出现。而第i个元素的贡献就是它左右分割点出现时间的最大值。

from https://blog.csdn.net/Icefox_zhx/article/details/80025305

注意如果有相同的数的时候，按照出现的position从小到大排序

（这破题搞了一上午我真是退役选手了）

//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

const int N=;

int n,mx[N],cnt[N];long long ans;

struct Nd{int w,p;}a[N];

bool cmp(Nd a,Nd b){if(a.w!=b.w)return a.w<b.w;return a.p<b.p;}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i].w),a[i].p=i;

    sort(a+,a++n,cmp);

    for(int i=;i<n;i++)mx[i]=max(mx[i-],a[i].p),cnt[i]=max(mx[i]-i,);

    for(int i=;i<=n;i++)ans+=max(cnt[i],cnt[i-]);

    printf("%lld\n",ans);

}

附一个暴力程序

//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

const int N=,inf=0x3f3f3f3f;

int n,a[N],work_counter,minn[N],maxx[N];

void bubble_sort_pass(int *a,int len){

    for(int i=;i<=len-;i++)if(a[i]>a[i+])swap(a[i],a[i+]);

}

int get_partition_points(int *a,int len){

    minn[len]=inf;maxx[]=a[];int temp=;

    for(int i=len-;~i;i--)minn[i]=min(minn[i+],a[i]);

    for(int i=;i<len;i++)maxx[i]=max(maxx[i-],a[i]);

    for(int i=;i<len-;i++)if(maxx[i]<=minn[i+])temp++;

    return temp;

}

void quickish_sort(int *a,int len){

    if(len==)return;

    work_counter+=len,bubble_sort_pass(a,len);

    minn[len]=inf;maxx[]=a[];int temp=;

    for(int i=len-;~i;i--)minn[i]=min(minn[i+],a[i]);

    for(int i=;i<len;i++)maxx[i]=max(maxx[i-],a[i]);

    vector<int>v;

    for(int i=;i<len-;i++)if(maxx[i]<=minn[i+])v.push_back(i);

    if(v.empty())return;

    quickish_sort(a,v[]+);

    for(int i=;i<v.size()-;i++)quickish_sort(a+v[i]+,v[i+]-v[i]);

    quickish_sort(a+v[v.size()-]+,len-v[v.size()-]-);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<n;i++)scanf("%d",&a[i]);

    quickish_sort(a,n);

    printf("%d\n",work_counter);

}