题解 | #The Grand Tournament#

首先把输入的序列dat[1...n] 映射成 序列id[1...n];
序列id[i]表示 原数组中第i个数是第id[i]大的数；
（特别地，如果原序列中两个数相等，那么按原数组下标从小到大排序）

题意即可转化为：从1..n扫描id序列。每次找出一段长度最小的区间，使得区间下标[i,j]里的值在id[i...j]出现且仅出现一次。求找到区间的个数。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxN = 1e6+10 ;
const int INF = 33333333 ;

struct Dat
{
    int v;
    int idx;
}dat[maxN];
int n;
int id[maxN];
int ans;

bool cmp(Dat a,Dat b)
{
    if(a.v<b.v)return a.v<b.v;
    else if(a.v==b.v)return a.idx<b.idx;
    return 0;
}

int main()
{
    cin>>n;

    for(int i =1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        dat[i].v = x;
        dat[i].idx = i;
    }

    sort(dat+1,dat+n+1,cmp);

    for(int i =1;i<=n;i++)id[dat[i].idx] = i;  

    int l = 1;                 //扫描时当前区间的左端点。
    int minv = INF,maxv = 0;
    for(int i =1;i<=n;i++)
    {
        minv = min(minv,id[i]);
        maxv = max(maxv,id[i]);
        if(maxv == i&&minv == l)
        {
            ans++;
            l = i+1;
            minv = INF;
            maxv = 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}