这题只要想出怎么建树就简单了吧。
他问的是连续k个值最大的是多少
就可以用1~k之和，2~k+1之和，3~k+2之和.......做为结点。
然后就发现，变成了简单的区间更新和区间查询问题了。
[cpp] #include #include #include #include #include #include #include #include #include #define eps 1e-5 #define MAXN 222222 #define MAXM 22222 #define INF 1000000007 #define lch(x) x<<1 #define rch(x) x<<1|1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int val[MAXN]; int n, k, m; int t[MAXN]; int mx[4 * MAXN], cover[4 * MAXN]; void up(int rt) { mx[rt] = max(mx[lch(rt)], mx[rch(rt)]); } void down(int rt) { if(cover[rt]) { cover[lch(rt)] += cover[rt]; cover[rch(rt)] += cover[rt]; mx[lch(rt)] += cover[rt]; mx[rch(rt)] += cover[rt]; cover[rt] = 0; } } void build(int l, int r, int rt) { cover[rt] = 0; if(l == r) { mx[rt] = t[l]; return; } int m = (l + r) >> 1; build(lson); build(rson); up(rt); } void update(int L, int R, int l, int r, int rt, int v) { if(L <= l && R >= r) { mx[rt] += v; cover[rt] += v; return; } down(rt); int m = (l + r) >> 1; if(m >= L) update(L, R, lson, v); if(m < R) update(L, R, rson, v); up(rt); } int query(int L, int R, int l, int r, int rt) { if(L <= l && R >= r) return mx[rt]; down(rt); int tmp = -INF; int m = (l + r) >> 1; if(m >= L) tmp = max(tmp, query(L, R, lson)); if(m < R) tmp = max(tmp, query(L, R, rson)); return tmp; } void change(int x, int y) { int st = x - k + 1, ed = x; if(st < 1) st = 1; update(st, ed, 1, n, 1, y - val[x]); val[x] = y; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) scanf("%d", &val[i]); t[1] = 0; for(int i = 1; i <= k; i++) t[1] += val[i]; for(int i = 2; i <= n - k + 1; i++) t[i] = t[i - 1] - val[i - 1] + val[i - 1 + k]; n = n - k + 1; build(1, n, 1); int op, x, y; while(m--) { scanf("%d%d%d", &op, &x, &y); if(op == 0) change(x, y); else if(op == 1) { int tmp = val[x]; change(x, val[y]); change(y, tmp); } else if(op == 2) printf("%d\n", query(x, y - k + 1, 1, n, 1)); } } return 0; }
#include #include #include #include #include #include #include #include #include #define eps 1e-5 #define MAXN 222222 #define MAXM 22222 #define INF 1000000007 #define lch(x) x<<1 #define rch(x) x<<1|1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int val[MAXN]; int n, k, m; int t[MAXN]; int mx[4 * MAXN], cover[4 * MAXN]; void up(int rt) { mx[rt] = max(mx[lch(rt)], mx[rch(rt)]); } void down(int rt) { if(cover[rt]) { cover[lch(rt)] += cover[rt]; cover[rch(rt)] += cover[rt]; mx[lch(rt)] += cover[rt]; mx[rch(rt)] += cover[rt]; cover[rt] = 0; } } void build(int l, int r, int rt) { cover[rt] = 0; if(l == r) { mx[rt] = t[l]; return; } int m = (l + r) >> 1; build(lson); build(rson); up(rt); } void update(int L, int R, int l, int r, int rt, int v) { if(L <= l && R >= r) { mx[rt] += v; cover[rt] += v; return; } down(rt); int m = (l + r) >> 1; if(m >= L) update(L, R, lson, v); if(m < R) update(L, R, rson, v); up(rt); } int query(int L, int R, int l, int r, int rt) { if(L <= l && R >= r) return mx[rt]; down(rt); int tmp = -INF; int m = (l + r) >> 1; if(m >= L) tmp = max(tmp, query(L, R, lson)); if(m < R) tmp = max(tmp, query(L, R, rson)); return tmp; } void change(int x, int y) { int st = x - k + 1, ed = x; if(st < 1) st = 1; update(st, ed, 1, n, 1, y - val[x]); val[x] = y; } int main() { in