CodeForces 548 D - Mike and Feet (단조 로 운 창고)

제목 링크https://vjudge.net/problem/CodeForces-548D
[제목] 한 조 의 길이 가 n 인 서열 a [1], a [2].
[사고] 단조 로 운 스 택 의 기초 응용 은 단조 로 운 스 택 은 O (n) 의 시간 안에 배열 중의 모든 요소 의 왼쪽 첫 번 째 가 그 보다 크 고 작은 요소 와 위 치 를 처리 할 수 있 습 니 다. 첫 번 째 오른쪽 이 그 보다 크 고 작은 요소 와 위 치 를 처리 할 수 있 습 니 다. 물론 이 문 제 는 우리 가 모든 요소 의 좌우 양쪽 첫 번 째 가 그 보다 작은 위 치 를 처리 하면 됩 니 다.예 를 들 어 우 리 는 a [i] 왼쪽 첫 번 째 부분 이 그 보다 작은 요 소 는 a [x] 이 고 오른쪽 첫 번 째 부분 이 그 보다 작은 위 치 는 a [y] 라 는 것 을 찾 았 다. 그러면 (x, y) 이 개방 구간 안에 a [i] 가 최소 치 라 는 것 을 설명 한다. a [i] 의 값 은 길이 = y - x - 1 (개방 구간 의 길이) 에 대응 하 는 답 이다. 모든 요 소 를 우리 가 이렇게 계산 하면 결 과 를 얻 을 수 있다.물론 어떤 길 이 는 우리 가 계산 하지 못 할 수도 있다. 예 를 들 어 아래 의 예 이다.
i
0
1
2
3
4
5
6
7
8
9
10
11
a[i]
-inf
1
2
3
4
5
5
3
2
1
6
-inf
le[i]
-1
0
1
2
3
4
4
2
1
0
9
-1
ri[i]
-1
11
9
8
7
7
7
8
9
11
11
-1
l, ri 는 각각 좌우 양쪽 의 첫 번 째 부분 이 현재 원소 의 아래 표 위치 보다 작다 (- 1 은 없다). 서열 의 시작 위치 와 끝 위치 에 두 개의 - inf 를 넣 으 면 마이너스 무한 대변 을 계산 하고 단조 로 운 창 고 를 이용 하여 위의 결 과 를 얻 은 후에 각 a [i] 를 순환 적 으로 계산 하고 길 이 를 (ri [i] - le [i] - 1) 의 답 을 최대 a [i] 로 업데이트 하면 된다.그리고 이런 결 과 를 얻 을 수 있 습 니 다.
len
1
2
3
4
5
6
7
8
9
10
ans
6
5
4
-1
3
-1
2
-1
-1
1
- 계산 되 지 않 은 길 이 를 나타 내 는데 이 길이 에 해당 하 는 답 은 얼마 일 까요?사실은 그들 오른쪽 에 있 는 첫 번 째 는 - 1 의 수치 가 아 닙 니 다. 즉, ans [4] = 3, ans [6] = 2, ans [8] = ans [9] = 1 입 니 다. 왜 일 까요?le, ri 배열 의 구체 적 인 의 미 를 생각해 보면 알 수 있 습 니 다. 우리 가 계산 한 (le [i], ri [i] 는 사실 가장 긴 구간 입 니 다. 이 구간 의 최소 치 는 a [i] 입 니 다. 이 구간 보다 더 긴 구간 길이 가 계산 되 지 않 았 다 면 그 답 은 가장 크 고 현재 의 답 과 같 을 수 밖 에 없습니다. 더 크 지 않 을 것 입 니 다. 왜냐하면 더 클 수 있다 면...반드시 그 전에 계 산 될 것 이다.

#include
using namespace std;

const int inf=2e9;
const int maxn=2e5+50;

int n;
int a[maxn];
stack<int> st;
int le[maxn],ri[maxn];
int ans[maxn];

void calc(){
    while(st.size()) st.pop();
    for(int i=0;i<=n+1;++i){
        while(st.size() && a[i]<=a[st.top()]) st.pop();
        if(st.empty()) le[i]=-1;
        else le[i]=st.top();
        st.push(i);
    }
    while(st.size()) st.pop();
    for(int i=n+1;i>=0;--i){
        while(st.size() && a[i]<=a[st.top()]) st.pop();
        if(st.empty()) ri[i]=-1;
        else ri[i]=st.top();
        st.push(i);
    }
}

int main(){
    scanf("%d",&n);
    a[0]=a[n+1]=-inf;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    calc();

    /*cout<

    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=n;++i){
        int len=ri[i]-le[i]-1;
        ans[len]=max(ans[len],a[i]);
    }
    for(int i=n;i>=0;--i) ans[i]=max(ans[i],ans[i+1]);

    for(int i=1;i<=n;++i){
        printf("%d%c",ans[i],i==n?'
':' ');
    }
    return 0;
}
/*
10
10 20 30 40 50 50 30 20 10 60
*/