题解：P13523 [KOI 2025 #2] 序列与查询

· · 题解

一句话题意：给一个长度为 n 的序列，m 次询问，每次询问时全局加上一个值后，询问你全局最大子段和。n,m\le 10^6。

看到最大子段和，我们自然想到使用 KTT 来解决这个问题。

考虑将询问离线，按照增量排序。然后按增量从小到大做。 于是问题就化为：全局加正数，询问全局最大子段和。

这个可以直接用 KTT 做，时间复杂度应该是 O(m\log^2n) 的，加上 fread 快读以及轻微的卡常可以轻松通过。

注意第一个询问的增量可能是负数，特判一下即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define pr pair<line,ll>
#define mk make_pair
#define fst first
#define snd second

char buf[1048576], *p1=buf, *p2=buf, ubuf[1048576], *u=ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++)

inline int read() {
    int x=0, f=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar())
        if(ch=='-') f=-1;
    for(; isdigit(ch); ch=getchar())
        x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

const int N=5e6+5;
const ll inf=LONG_LONG_MAX;

int n, m, a[N], tg[N<<2], res, tot;
ll ans[N];

struct qs {
    int id, add;
} q[N];

struct line {
    ll a, b;
    friend line operator+(line a, line b) {
        return {a.a+b.a, a.b+b.b};
    }
};

inline pr maxf(line x, line y) {
    if(x.a<y.a || (x.a==y.a && x.b<y.b))
        swap(x, y);
    if(x.b>=y.b)
        return mk(x, inf);
    return mk(y, (y.b-x.b)/(x.a-y.a));
}

struct KTT {
    line lmx, rmx, s, ans;
    ll intr;

    #define lmx(z) t[z].lmx
    #define rmx(z) t[z].rmx
    #define s(z) t[z].s
    #define ans(z) t[z].ans
    #define intr(z) t[z].intr

    friend KTT operator+(KTT x, KTT y) {
        KTT res;
        pr g;

        res.s = x.s + y.s;
        res.intr = min(x.intr, y.intr);

        g = maxf(x.lmx, x.s + y.lmx);
        res.lmx = g.fst;
        res.intr = min(res.intr, g.snd);

        g = maxf(y.rmx, y.s + x.rmx);
        res.rmx = g.fst;
        res.intr = min(res.intr, g.snd);

        g = maxf(y.ans, x.ans);
        res.intr = min(res.intr, g.snd);

        g = maxf(g.fst, x.rmx + y.lmx);
        res.intr = min(res.intr, g.snd);
        res.ans = g.fst;

        return res;
    }
} t[N<<2];

inline void build(int k, int l, int r) {
    tg[k] = 0;
    if(l == r)
        return (void)(intr(k)=inf, lmx(k)=rmx(k)=s(k)=ans(k)={1, a[l]});

    ll mid = l + r >> 1;
    build(k<<1, l, mid);
    build(k<<1|1, mid+1, r);
    t[k] = t[k<<1] + t[k<<1|1];
}

inline void Add(int k, int v) {
    tg[k] += v;
    intr(k) -= v;
    lmx(k).b += lmx(k).a * v;
    rmx(k).b += rmx(k).a * v;
    s(k).b += s(k).a * v;
    ans(k).b += ans(k).a * v;
}

inline void pushdown(int k) {
    if(!tg[k]) return;
    Add(k<<1, tg[k]);
    Add(k<<1|1, tg[k]);
    tg[k] = 0;
}

inline void rebuild(int k) {
    if(intr(k) >= 0) return;
    pushdown(k);
    rebuild(k<<1);
    rebuild(k<<1|1);
    t[k] = t[k<<1] + t[k<<1|1];
}

inline void upt(int k, int x, int y, int v, int l, int r) {
    if(x <= l && r <= y)
        return (void)(Add(k, v), rebuild(k));

    int mid = l + r >> 1;
    pushdown(k);

    if(mid >= x)
        upt(k<<1, x, y, v, l, mid);
    if(mid+1 <= y)
        upt(k<<1|1, x, y, v, mid+1, r);

    t[k] = t[k<<1] + t[k<<1|1];
}

inline KTT que(int k, int x, int y, int l, int r) {
    if(x <= l && r <= y)
        return t[k];

    int mid = l + r >> 1;
    pushdown(k);

    if(y <= mid)
        return que(k<<1, x, y, l, mid);
    if(mid < x)
        return que(k<<1|1, x, y, mid+1, r);

    return que(k<<1, x, y, l, mid) + que(k<<1|1, x, y, mid+1, r);
}

inline bool cmp(qs a, qs b) {
    return a.add < b.add;
}

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    n = read();
    m = read();

    for(int i=1; i<=n; i++)
        a[i] = read();

    for(int x; m--;) {
        x = read();
        q[++tot] = {tot, x};
    }

    sort(q+1, q+tot+1, cmp);

    for(int i=1; i<=n; i++)
        a[i] += q[1].add;

    build(1, 1, n);
    ans[q[1].id] = que(1, 1, n, 1, n).ans.b;

    for(int i=2; i<=tot; i++) {
        if(q[i].add != q[i-1].add)
            upt(1, 1, n, q[i].add - q[i-1].add, 1, n);
        ans[q[i].id] = t[1].ans.b;
    }

    for(int i=1; i<=tot; i++)
        cout << ans[i] << endl;

    return 0;
}

同样的做法还可以做 P5073，只需将全局查询改为区间查询就行。