连号区间数

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1 ~ NN 的某个全排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L, R][L,R] 里的所有元素（即此排列的第 LL 个到第 RR 个元素）递增排序后能得到一个长度为 R-L+1R−L+1 的"连续"数列，则称这个区间连号区间。

当 NN 很小的时候，小明可以很快地算出答案，但是当 NN 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入描述

第一行是一个正整数 N (1 \leq N \leq 50 \times 10^4)N(1≤N≤50×104), 表示全排列的规模。

第二行是 NN 个不同的数字 P_i\ (1 \leq P_i \leq N)Pi​ (1≤Pi​≤N)，表示这 NN 个数字的某一全排列。

输出描述

输出一个整数，表示不同连号区间的数目。

输入输出样例

示例

输入

4
3 2 4 1

输出

7

c语言

#include <stdio.h>
#include <stdlib.h>
long long INF=1e9;
 
int max(int a,int b)
{
  return a>b?a:b;
}
int min(int a,int b)
{
  return a<b?a:b;
}//c++可以直接不写比较大小函数，有现成的
int main(int argc, char *argv[])
{
   int n;
   int p[1000000];
   long long res=0;
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   {
     scanf("%d",&p[i]);
   }
 
   for(int i=0;i<n;i++)
   {
      int maxv=-INF,minv=INF;
     for(int j=i;j<n;j++)
     {
      //  int max=-INF,min=INF;err
      //注意摆放位置，是每次左边界的一开始给max，min附上第一个数
      //   min=(min,p[j]);
      // max=(max,p[j]);函数都不用写了是吧？
      //为了避免和函数混淆，取名字特意改一下
 
       minv=min(minv,p[j]);
      maxv=max(maxv,p[j]);//迭代
      
      //左边界没有变的时候，每次都保留这次的minv与maxv
      //然后跟最新的数字比较，有更好的就更新，没更好的就保留
      //避免重复遍历.
 
       if(maxv-minv==j-i)
       {
         res++;
       }
     }
   }
 
   printf("%lld",res);
  return 0;
}
//不能给p排序，因为题目说的是排序后可以得到，而不是让你排序
//你排了序选定的数字位置都不一样了，是选定后排，而不是先排后选定
//所以不需要给输入的数字排序

 c++解析

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, INF = 100000000;
int n;
int a[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
		cin >> a[i];
    int res = 0;
    for (int i = 0; i < n; i ++ )  //开始 
    {
        int minv = INF, maxv = -INF;
        for (int j = i; j < n; j ++ )  //结尾    
        {
            minv = min(minv, a[j]);
            maxv = max(maxv, a[j]);//迭代
            
            if (maxv - minv == j - i) res ++ ;
        }
    }
    cout << res << endl;
    return 0;
}
//因为是第L到第R，而且是区间跟子字符串是一样的，不能跳跃分割，只能按每个数字按从左到右的顺序遍历
//题目要求是连续数列。
//因此遍历情况就是从左边界0开始，依次划定右边界范围，然后从1开始，从2开始依次检索
//区间的L,R是数字大小，长度是下标的比较，因为排序，所以意思就是判断是否最大于最小只差==初末下标差
//迭代也是，一般连续的才适用.