学步园

SPOJ_1716

    这个题目和SPOJ_1043的GSS1是类似的，只不过增加了单点修改的功能。用线段树实现相应的功能即可。

#include<stdio.h>
#include<string.h>
#define MAXD 50010
#define INF 0x3f3f3f3f3f3f3f3fll
int N, M, a[MAXD];
long long lc[4 * MAXD], rc[4 * MAXD], mc[4 * MAXD], sum[4 * MAXD];
long long Max(long long x, long long y)
{
    return x > y ? x : y;
}
void update(int cur)
{
    int ls = cur << 1, rs = cur << 1 | 1;
    sum[cur] = sum[ls] + sum[rs];
    mc[cur] = Max(mc[ls], mc[rs]);
    mc[cur] = Max(mc[cur], rc[ls] + lc[rs]);
    lc[cur] = Max(lc[ls], sum[ls] + lc[rs]);
    rc[cur] = Max(rc[rs], sum[rs] + rc[ls]);
}
void build(int cur, int x, int y)
{
    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;
    if(x == y)
    {
        sum[cur] = mc[cur] = lc[cur] = rc[cur] = a[x];
        return ;
    }
    build(ls, x, mid);
    build(rs, mid + 1, y);
    update(cur);
}
void refresh(int cur, int x, int y, int k, int v)
{
    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;
    if(x == y)
    {
        sum[cur] = mc[cur] = lc[cur] = rc[cur] = v;
        return ;
    }
    if(k <= mid)
        refresh(ls, x, mid, k, v);
    else
        refresh(rs, mid + 1, y, k, v);
    update(cur);
}
long long Search(int cur, int x, int y, int s, int t, long long &ans, int flag)
{
    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;
    if(x >= s && y <= t)
    {
        ans = Max(ans, mc[cur]);
        return flag ? rc[cur] : lc[cur];
    }
    if(mid >= t)
        return Search(ls, x, mid, s, t, ans, 0);
    else if(mid + 1 <= s)
        return Search(rs, mid + 1, y, s, t, ans, 1);
    long long ln, rn;
    ln = Search(ls, x, mid ,s, t, ans, 1), rn = Search(rs, mid + 1, y, s, t, ans, 0);
    ans = Max(ans, ln + rn);
    if(flag)
        return Max(sum[rs] + ln, rc[rs]);
    else
        return Max(sum[ls] + rn, lc[ls]);
}
void init()
{
    int i;
    for(i = 1; i <= N; i ++)
        scanf("%d", &a[i]);
    build(1, 1, N);
}
void solve()
{
    int i, k, x, y, q;
    long long ans;
    scanf("%d", &q);
    for(i = 0; i < q; i ++)
    {
        scanf("%d%d%d", &k, &x, &y);
        if(k == 0)
            refresh(1, 1, N, x, y);
        else
        {
            ans = -INF;
            Search(1, 1, N, x, y, ans, 0);
            printf("%lld\n", ans);
        }
    }
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;
}