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

题目链接

其实写线段树的题还是比较的令我开心的因为不用脑子

怎么判断这题是要写线段树的？

1.暴力只能拿50分

2.这题是个绿题

3 .看数据范围

#include <cstdio>

#include <iostream>

#define lson k << 1

#define rson k << 1 | 1

using namespace std;

const int N = ;

int n, m, c, minx, maxx;

bool flag;

struct node{

    int l, r, minn, maxn, w;

}tr[N << ];

int read() {

    int s = , w = ;

    char ch = getchar();

    while(!isdigit(ch)) {if(ch == '-') w = -;ch = getchar();}

    while(isdigit(ch)) {s = s *  + ch - '';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) >> ;

    build(lson, ll, mid);

    build(rson, mid + , 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) >> ;

    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(, , n);

    for(int i = ; i + m -  <= n; i++) {

        minx = 0x3f3f3f3f, maxx = -0x3f3f3f3f;

        ask_query(, i, i + m - );

        if(maxx - minx <= c)

            printf("%d\n", i), flag = ;

    }

    if(!flag) printf("NONE\n");

    return ;

}

谢谢收看，祝身体健康！