【题解】分组排序

题意

给你一个长度为且各个元素不同的序列，问将序列，划分为连续的段，对每段内部进行从小到大排序，然后将各个段按顺序拼接起来，求让整体是从小到大有序的。

题解

由于序列中的每个数都不同，可以将元素映射到。排序完之后就是的形式。那么也就是的值是多少，那么他最后的下标也是。从这个性质上来看，我们对于每个数字可以将其现在的位置与排序后所在的位置看成一段区间，也就是说每个数字可以有一段区间。若两段区间之间有交叉也就是排序时两个区间必须合并。所以我们可以将区间按左端点进行排序之后从头到尾合并一下，最后剩下几个不重叠的区间也就是要找的最大的。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node
{
    int l,r;
}d[N];
int a[N];
int b[N];
map<int,int>vis;
bool cmp(node a,node b)
{
    return a.l<b.l;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b,b+n);
    for(int i=0;i<n;i++)
        vis[b[i]]=i;
    for(int i=0;i<n;i++)
    {
        d[i].l=min(i,vis[a[i]]);
        d[i].r=max(i,vis[a[i]]);
    }
    sort(d,d+n,cmp);
    int ans=1;
    node merged=d[0];
    for(int i=1;i<n;i++)
    {
        if(merged.r<d[i].l)
        {
            merged=d[i];
            ans++;
        }
        else
        {
            merged.r=max(d[i].r,merged.r);
        }
    }
    printf("%d\n",ans);
    return 0;
}