本文共 3497 字，大约阅读时间需要 11 分钟。
题意：在l,r区间找到 最靠近左边的和最大区间。
要理清思路写。简单区间合并。查找要麻烦点，三个查找函数，分别是向左范围内最大连续，向右范围内最大连续，整体最大连续。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 555555;const LL INF = 1844674407370955161LL;LL sum[maxn << 2], Max[maxn << 2], rmax[maxn << 2], lmax[maxn << 2];int rl[maxn << 2], lr[maxn << 2], rpos[maxn << 2], lpos[maxn << 2], tfr[maxn << 2], tfl[maxn << 2];int fl[maxn << 2], fr[maxn << 2];void up(int l, int r, int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; lmax[rt] = lmax[rt << 1]; rmax[rt] = rmax[rt << 1 | 1]; lr[rt] = lr[rt << 1]; rl[rt] = rl[rt << 1 | 1]; LL k = rmax[rt << 1] + lmax[rt << 1 | 1]; if (sum[rt << 1] + lmax[rt << 1 | 1] > lmax[rt]){ lmax[rt] = sum[rt << 1] + lmax[rt << 1 | 1]; lr[rt] = lr[rt << 1 | 1]; } if (sum[rt << 1 | 1] + rmax[rt << 1] > rmax[rt << 1 | 1]){ rmax[rt] = sum[rt << 1 | 1] + rmax[rt << 1]; rl[rt] = rl[rt << 1]; } if (lmax[rt] >= k&&lmax[rt] >= rmax[rt]){ Max[rt] = lmax[rt]; lpos[rt] = l; rpos[rt] = lr[rt]; } else if (k >= lmax[rt] && k >= rmax[rt]){ Max[rt] = k, lpos[rt] = rl[rt << 1], rpos[rt] = lr[rt << 1 | 1]; } else Max[rt] = rmax[rt], lpos[rt] = rl[rt], rpos[rt] = r;}void build(int l, int r, int rt){ if (l == r){ LL t; scanf("%lld",&t); sum[rt] = Max[rt] = lmax[rt] = rmax[rt] = t; lpos[rt]=rpos[rt]=lr[rt] = rl[rt] = l; return; } int mid = (l + r) >> 1; build(lson); build(rson); up(l, r, rt);}LL asks(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R) return sum[rt]; int mid = (l + r) >> 1; LL ans = 0; if (L <= mid) ans += asks(L, R, lson); if (R > mid) ans += asks(L, R, rson); return ans;}LL askl(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R) { tfr[rt] = lr[rt]; return lmax[rt]; } int mid = (l + r) >> 1; LL ans1 = -INF; LL ans2 = -INF; if (L <= mid) ans1 = askl(L, R, lson); if (R > mid) ans2 = askl(L, R, rson); LL k = asks(L, R, lson); if (ans1 >= ans2 + k){ tfr[rt] = tfr[rt << 1]; return ans1; } else { tfr[rt] = tfr[rt << 1 | 1]; return ans2 + k; }}LL askr(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R){ tfl[rt] = rl[rt]; return rmax[rt]; } int mid = (l + r) >> 1; LL ans1 = -INF; LL ans2 = -INF; if (L <= mid) ans1 = askr(L, R, lson); if (R > mid) ans2 = askr(L, R, rson); LL k = asks(L, R, rson); if (k + ans1 >= ans2){ tfl[rt] = tfl[rt << 1]; return k + ans1; } else{ tfl[rt] = tfl[rt << 1 | 1]; return ans2; }}LL ask(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R){ fl[rt] = lpos[rt]; fr[rt] = rpos[rt]; return Max[rt]; } int mid = (l + r) >> 1; LL ans = -INF; if (L <= mid){ LL k = ask(L, R, lson); if (k > ans){ ans = k; fl[rt] = fl[rt << 1]; fr[rt] = fr[rt << 1]; } } if (L <= mid&&R > mid){ LL ans1 = askl(mid+1, R, rson); LL ans2 = askr(L, mid, lson); int tl = tfl[rt<<1]; int tr = tfr[rt<<1|1]; if (ans1 + ans2 > ans) { ans = ans1 + ans2; fl[rt] = tl; fr[rt] = tr; } } if (R > mid){ LL k = ask(L, R, rson); if (k > ans){ ans = k; fl[rt] = fl[rt << 1 | 1]; fr[rt] = fr[rt << 1 | 1]; } } return ans;}int main(){ int n, m, l, r; int Icase = 0; while (cin >> n >> m){ build(1, n, 1); printf("Case %d:\n", ++Icase); for (int i = 0; i < m; i++){ scanf("%d%d", &l, &r); int t = ask(l, r, 1, n, 1); printf("%d %d\n", fl[1], fr[1]); } } return 0;}
转载于:https://www.cnblogs.com/yigexigua/p/4024100.html