낙 곡 [P1440] m 구간 내 최소 값 구하 기 (단조 대기 열)

링크
https://www.luogu.org/problem/P144
제목
n n n 의 길 이 를 가 진 서열 a a a 를 드 리 겠 습 니 다. a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i]] 이전의 m m 개수 중 가장 작은 값 인 [i - m, i - 1] [i - m, i - 1] [i - m, i - 1] [i - m, i - 1] [i - 1], i - 1] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i] a [i]] a [i] a [i]] a [i] a [i]] a [i]] a [i] 값.
분석 하 다.
길이 m m 의 창 을 단조 로 운 대기 열 로 유지 하면 됩 니 다.읽 기 마 운 트 를 사용 하 세 요. cin 을 사용 하지 마 세 요. 그렇지 않 으 면 시간 을 초과 할 수 있 습 니 다.
코드
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define INF 0x7f7f7f7f
#define MAXN 2000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, m, t1, t2, a[MAXN], q[MAXN];

int main() {
    cin >> n >> m;
    //cin >> a[1];
    //cout << 0 << endl;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        if (i == 1) {
            printf("0
"
); q[++t2] = i; t1++; continue; } printf("%d
"
, a[q[t1]]); while (t1 <= t2 && a[i] < a[q[t2]]) { t2--; } q[++t2] = i; //cout << q[t2] << " " << q[t1] << endl; while (q[t2] - q[t1] + 1 > m) { t1++; } } }

좋은 웹페이지 즐겨찾기