[제4 회 블 루 브리지 컵 주 경기 C + + B 조] 연호 구간 수

출처: 제4 회 블 루 브리지 컵 성 경기 C + B 조
알고리즘 태그 매 거
제목 설명
샤 오 밍 은 요 며칠 동안 이런 이상 하고 재 미 있 는 문 제 를 생각 하고 있다.
1 ∼ N 의 한 배열 에는 몇 개의 연호 구간 이 있 습 니까?
여기 서 말 하 는 연결 구간 의 정 의 는:
구간 [L, R] 에 있 는 모든 원소 (즉 이 배열 의 L 번 째 부터 R 번 째 원소) 가 점차 정렬 을 늘 린 후 길이 가 R − L + 1 인 '연속' 수열 을 얻 을 수 있다 면 이 구간 의 연호 구간 이 라 고 한다.
N 이 아주 어 렸 을 때 샤 오 밍 은 빠르게 답 을 계산 할 수 있 었 지만 N 이 커 졌 을 때 문 제 는 그리 간단 하지 않 았 다. 지금 샤 오 밍 은 너의 도움 이 필요 하 다.
입력 형식
첫 줄 은 정수 N 으로 배열 의 규 모 를 나타 낸다.
두 번 째 줄 은 N 개의 서로 다른 숫자 Pi 로 이 N 개의 숫자의 특정한 배열 을 나타 낸다.
출력 형식
하나의 정 수 를 출력 하여 서로 다른 연결 구간 의 수 를 나타 낸다.
데이터 범위
1≤N≤10000, 1≤Pi≤N
입력 샘플 1:
4 3 2 4 1
출력 예시 1:
7
입력 샘플 2:
5 3 4 2 5 1
출력 예시 2:
9
예 를 들 어 해석 하 다.
첫 번 째 용례 중 7 개의 연호 구간 은 [1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4] 두 번 째 용례 중 9 개의 연호 구간 은 [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 2], [2, 2], [3, 3], [4, 4], [5, 5] 이다.
사고의 방향
구간 [L, R] 에 있 는 모든 원소 (즉 이 배열 의 L 번 째 부터 R 번 째 원소) 가 점차 정렬 을 늘 린 후 길이 가 R − L + 1 인 '연속' 수열 을 얻 을 수 있다 면 이 구간 의 연호 구간 이 라 고 한다.
입력 샘플 1:
4 3 2 4 1
첫 번 째 용례 중 7 개의 연결 구간 은 [1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4] 이다.
1. 연결 번 호 는 A. 단조 로 운 증가 서브 시퀀스 B. 자신 을 만족 시 켜 야 하기 때 문 입 니 다. 임의의 서브 시퀀스 에 있 는 숫자 는 반드시 사용 되 어야 단조 로 운 증가 서브 시퀀스 에 부합 한 다 는 것 을 나 타 낼 수 있 기 때 문 입 니 다. 3. 좌우 두 개의 점 순환 을 모 의 하면 오른쪽 점 - 왼쪽 점 은 현재 최대 치 와 같 습 니 다. - 현재 최소 치 는 왼쪽 점 에서 오른쪽 점 까지 의 모든 수 를 단조 로 운 증가 서브 시퀀스 로 사용 합 니 다.(그리고 이 상황 은 a [i] - a [i] 에 똑 같이 적용 되면 정 답 + 1
모든 구간 을 매 거 하여 최대 치 를 최소 치 로 줄 이 는 것 이 구간 길이 와 같다 면 모든 데 이 터 를 다 사용 하고 연 호 를 표시 하 는 것 은 연호 구간 이다.
C + + 코드

#include

using namespace std;
const int N=1e4+10,INF=1e8;
int a[N];

int main()
{
     
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    int cnt=0;
    for(int i=1;i<=n;i++)   
        {
     
            int maxv=-INF,minv=INF;
            for(int j=i;j<=n;j++)
                {
     
                    maxv=max(a[j],maxv),minv=min(a[j],minv);
                    if(maxv-minv==j-i)cnt++;
                }
        }
    cout<<cnt;
    return 0;
}