1400 - "Ray, Pass me the dishes!"
第一次做线段树题目，确实一点也不会，想了很久，首先是线段树怎么作用，每一步会产生什么影响。首先，线段树的每次更新都更新了什么，为什么要这么更新，尤其是更新的区间，虽说原理很简单，就是要么在左子树，要么在右子树，要么兼顾左右子树，所以如果是在左子树，那就查找左子树，否则右子树，或者左右子树都查找，再合并左右子树，这仅是对于查找而言的。那么建树是怎么回事呢，首先建树必然会包括所有情况，每种情况事实上的是在这个过程中不断更新，事实上就是符合每次区间[l, r]的查找罢了，就是特殊情况处理了，然后再从特殊情况中拼凑出非特殊情况就可以了#include <iostream>#include <stack>#include <queue>#include <cstdio>#include <cstdlib>#include <cmath>#include <set>#include <vector>#include <cstring>#include <algorithm>#define INF 0x7ffffffffffLL#define N 500010#define LL long long#define mod 95041567using namespace std;struct node{ LL MAX, MAX_PREFIX, MAX_SUFFIX; int l, r, ll, rr;};LL sum[N];node G[N << 2];void pushup(int L, int R, int rt){ int mid = (R - L) / 2 + L; G[rt].MAX_PREFIX = G[rt << 1].MAX_PREFIX, G[rt].ll = G[rt << 1].ll; if(G[rt].MAX_PREFIX < G[(rt << 1) | 1].MAX_PREFIX + sum[mid] - sum[L - 1]){ G[rt].MAX_PREFIX = G[(rt << 1) | 1].MAX_PREFIX + sum[mid] - sum[L - 1]; G[rt].ll = G[(rt << 1) | 1].ll; } G[rt].MAX_SUFFIX = G[(rt << 1) | 1].MAX_SUFFIX, G[rt].rr = G[(rt << 1) | 1].rr; if(G[rt].MAX_SUFFIX <= G[rt << 1].MAX_SUFFIX + sum[R] - sum[mid]){ G[rt].MAX_SUFFIX = G[rt << 1].MAX_SUFFIX + sum[R] - sum[mid]; G[rt].rr = G[rt << 1].rr; } G[rt].MAX = G[rt << 1].MAX, G[rt].l = G[rt << 1].l, G[rt].r = G[rt << 1].r; if(G[(rt << 1) | 1].MAX > G[rt].MAX){ G[rt].MAX = G[(rt << 1) | 1].MAX; G[rt].l = G[(rt << 1) | 1].l; G[rt].r = G[(rt << 1) | 1].r; } if(G[rt].MAX < G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX){ G[rt].MAX = G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX; G[rt].l = G[rt << 1].rr; G[rt].r = G[(rt << 1) | 1].ll; } else if(G[rt].MAX == G[rt << 1].MAX_SUFFIX + G[(rt << 1) | 1].MAX_PREFIX){ if(G[rt].l > G[rt << 1].rr){ G[rt].l = G[rt << 1].rr; G[rt].r = G[(rt << 1) | 1].ll; } else if(G[rt].l == G[rt << 1].rr && G[rt].r > G[(rt << 1) | 1].ll) G[rt].r = G[(rt << 1) | 1].ll; }}void build_tree(int L, int R, int rt){ if(L == R){ G[rt].l = G[rt].r = L; G[rt].ll = G[rt].rr = L; G[rt].MAX = G[rt].MAX_SUFFIX = G[rt].MAX_PREFIX = sum[L] - sum[L - 1]; return; } int mid = (R - L) / 2 + L; build_tree(L, mid, rt << 1); build_tree(mid + 1, R, (rt << 1) | 1); pushup(L, R, rt);}node query(int L, int R, int rt, int l, int r){ if(L == l && R == r) return G[rt]; int mid = (R - L) / 2 + L; if(mid < l) return query(mid + 1, R, (rt << 1) | 1, l, r); if(r <= mid) return query(L, mid, rt << 1, l, r); node ln = query(L, mid, rt << 1, l, mid); node rn = query(mid + 1, R, (rt << 1) | 1, mid + 1, r); node v = ln; if(v.MAX < rn.MAX) v = rn; if(v.MAX < ln.MAX_SUFFIX + rn.MAX_PREFIX){ v.MAX = ln.MAX_SUFFIX + rn.MAX_PREFIX; v.l = ln.rr; v.r = rn.ll; } else if(v.MAX == ln.MAX_SUFFIX + rn.MAX_PREFIX){ if(v.l > ln.rr){ v.l = ln.rr; v.r = rn.ll; } else if(v.l == ln.rr && v.r > rn.ll) v.r = rn.ll; } v.MAX_PREFIX = ln.MAX_PREFIX, v.ll = ln.ll; v.MAX_SUFFIX = rn.MAX_SUFFIX, v.rr = rn.rr; if(v.MAX_PREFIX < sum[mid] - sum[l - 1] + rn.MAX_PREFIX){ v.MAX_PREFIX = sum[mid] - sum[l - 1] + rn.MAX_PREFIX; v.ll = rn.ll; } if(v.MAX_SUFFIX <= sum[r] - sum[mid] + ln.MAX_SUFFIX){ v.MAX_SUFFIX = sum[r] - sum[mid] + ln.MAX_SUFFIX; v.rr = ln.rr; } return v;}int main(){ // freopen("in.txt","r",stdin); int m, n, t = 1; sum[0] = 0; while(scanf("%d %d", &n, &m) != EOF){ for(int i = 1; i <= n; ++i){ scanf("%lld", &sum[i]); sum[i] += sum[i - 1]; } build_tree(1, n, 1); printf("Case %d:\n", t++); int l, r; for(int i = 0; i < m; ++i){ scanf("%d %d", &l, &r); node v = query(1, n, 1, l, r); printf("%d %d\n", v.l, v.r); } } return 0;}