洛谷题解 P4392 【[BOI2007]Sound 静音问题】

#include <cstdio>
#include <iostream>
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int N = 2000000;
int n, m, c, minx, maxx;
bool flag;
struct node{
    int l, r, minn, maxn, w;
}tr[N << 2];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == ‘-‘) w = -1;ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - ‘0‘;ch = getchar();}
    return s * w;
}
void build(int k, int ll, int rr) {
    tr[k].l = ll, tr[k].r = rr;
    if(ll == rr) {tr[k].w = read();tr[k].maxn = tr[k].minn = tr[k].w;return;}
    int mid = (ll + rr) >> 1;
    build(lson, ll, mid);
    build(rson, mid + 1, rr);
    tr[k].minn = min(tr[lson].minn, tr[rson].minn);
    tr[k].maxn = max(tr[lson].maxn, tr[rson].maxn);
}
void ask_query(int k, int x, int y) {
    if(tr[k].l >= x && tr[k].r <= y) {minx = min(minx, tr[k].minn);maxx = max(maxx, tr[k].maxn);return;}
    int mid = (tr[k].l + tr[k].r) >> 1;
    if(x <= mid) ask_query(lson, x, y);
    if(y > mid) ask_query(rson, x, y);
}
int main() {
    n = read(), m = read(), c = read();
    build(1, 1, n);
    for(int i = 1; i + m - 1 <= n; i++) {
        minx = 0x3f3f3f3f, maxx = -0x3f3f3f3f;
        ask_query(1, i, i + m - 1);
        if(maxx - minx <= c)
            printf("%d\n", i), flag = 1;    
    }
    if(!flag) printf("NONE\n");
    return 0;
}