其实写线段树的题还是比较的令我开心的因为不用脑子
怎么判断这题是要写线段树的？
1.暴力只能拿50分
2.这题是个绿题
3 .看数据范围
#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; }
谢谢收看，祝身体健康！