HDU 6319 문제 풀이 (데이터 구조의 양 끝 대기 열)

제목 링크: 제목 보기 여기 ~
제목: 하나의 시퀀스 a [1. n] 를 지정 하고 각 길이 가 m 인 연속 서브 구간 에 대해 구간 a 의 최대 값 과 왼쪽 에서 오른쪽으로 이 구간 을 스 캔 할 때 a 의 최대 값 변화 횟수 를 구 합 니 다.(실제로 이것 을 출력 하 는 것 이 아니 라 구체 적 으로 원 제 를 보 세 요)
1 ≤ m ≤ n ≤ 107 
문제 풀이:
2 단 대기 열 을 사용 하여 오른쪽 에서 왼쪽으로 단조 로 운 비 체감 대기 열 을 유지 합 니 다.구간 [l, l + m) 에서 [l - 1, l + m - 1) 로 미 끄 러 질 때 a [l - 1] < = a [l] 는 a [l - 1] 에 직접 대열 의 선두 에 삽입 하고 a [l - 1] > a [i] 는 대열 의 선두 에서 a [l - 1] 보다 작은 값 pop 을 떨 어 뜨 린 다음 a [i - 1] 을 팀 의 선두 에 꽂 습 니 다. a [l + m - 1] 이 라면.팀 꼬리 요소 와 같 으 면 팀 꼬리 pop 을 떨 어 뜨 립 니 다. 기다 리 지 않 으 면 상관 하지 않 아 도 됩 니 다. push 마다 반복 되 지 않 는 요소, cnct + 1, pop 마다 숫자 와 모든 중복 부분, cnct - 1 을 떨 어 뜨 립 니 다.
이렇게 하면 모든 요 소 는 push 한 번, pop 한 번, 시간 복잡 도 O (n) 에 불과 합 니 다.
AC 코드:

#include
#include
#include
#include