古明地枣何许人也

pystraf11 · 2025-12-03 17:02:28 · 题解

Description

给定 n 个二元组 (x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)。

Solution

将操作变为单点加，求最大后缀和。

这里要注意，由于初值为 0，但答案没说向 0 取 \max，所以要把 全局 操作提出来，用前缀和预处理后每次询问 单独算。

在 a 中，显然只有被修改过的位置有用。那么将二元组按照 x_i 升序 排序，x_i 相同的按照 y_i 降序 排序（为了保证对同个 x_i 的操作能全部被取到）。

设 p_i 表示 排序后 的第 i 个二元组的 原下标。那么每次询问就是求：

直接套用 P5611 做法，对二元组分块，并对每块做 O(B^2) 分治预处理，询问将每块答案合并即可，时间复杂度 O(n\sqrt n)。

::::info[code]

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

namespace Fastio {}
using Fastio::qin;
using Fastio::qout;

struct Info {
    i64 suf, sum;
    Info() { suf = sum = 0; }
    Info(i64 a, i64 b) : suf(a), sum(b) {}
};

inline Info operator+(const Info& a, const Info& b) {
    Info c;
    c.suf = max(b.suf, b.sum + a.suf);
    c.sum = a.sum + b.sum;
    return c;
}

constexpr int B = 512;
struct Query {
    int l, r, L, R;
    inline Query() {}
    inline Query(int l, int r, int L, int R) : l(l), r(r), L(L), R(R) {}
};

struct Block {
    array<vector<vector<Info>>, B * 2 + 10> ans;
    array<vector<int>, B * 2 + 10> v;
    array<int, B * 2 + 10> posa, posb;

    inline void merge(int a, int b, int k) {
        int _v, siz = 0, _a = 0, _b = 0, p = 0;
        int siza = v[a].size(), sizb = v[b].size(), sizk = v[k].size();
        for (int i = 0; i < siza; i++) {
            _v = v[a][i];
            while (p < sizb && v[b][p] <= _v) v[k][siz] = v[b][p++], siz++;
            v[k][siz] = _v, siz++;
        }
        while (p < sizb) v[k][siz] = v[b][p++], siz++;

        for (int i = 0; i < sizk; i++) {
            _v = v[k][i];
            while (_a < siza && v[a][_a] <= _v) _a++;
            while (_b < sizb && v[b][_b] <= _v) _b++;
            posa[i] = _a, posb[i] = _b;
        }

        _a = _b = 0;
        for (int l = 0; l < sizk; l++) {
            _v = v[k][l];
            while (_a < siza && v[a][_a] < _v) _a++;
            while (_b < sizb && v[b][_b] < _v) _b++;
            for (int r = l; r < sizk; r++)
                ans[k][l + 1][r + 1] = ans[a][_a + 1][posa[r]] + ans[b][_b + 1][posb[r]];
        }
    }

    void alloc(int u, int l, int r) {
        int len = r - l + 1;
        ans[u].resize(len + 2);
        for (auto & v : ans[u]) v.resize(len + 2);
        v[u].resize(len);
        if (l == r) return;
        int mid = (l + r) >> 1;
        alloc(u << 1, l, mid), alloc(u << 1 | 1, mid + 1, r);
    }

    void init() { alloc(1, 0, B - 1); }
    Info qry(int l, int r) { return ans[1][l][r]; }

    void build() {
        for (int i = B - 1; i >= 1; i--) merge(i << 1, i << 1 | 1, i);
    }
};

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

    int n, q;
    qin >> n >> q;

    vector<int> X(n), Y(n), id(n);
    vector<i64> pre(n + 1);
    for (int i = 0; i < n; i++) {
        qin >> X[i] >> Y[i], X[i]--;
        pre[i + 1] = pre[i], id[i] = i;
        if (X[i] == n - 1) pre[i + 1] += Y[i], Y[i] = 0;
    }

    vector<int> L(q), R(q);
    for (int i = 0; i < q; i++) {
        qin >> L[i] >> R[i];
        L[i]--, R[i]--;
    }

    sort(id.begin(), id.end(), [&](int x, int y) {
        return X[x] == X[y] ? Y[x] > Y[y] : X[x] < X[y];
    });

    vector<int> seq(n);
    for (int i = 0; i < n; i++) seq[i] = Y[id[i]];

    Block ds; ds.init();
    vector<int> h;

    auto init = [&](int bl, int br) {
        int len = br - bl + 1;
        for (int i = 0; i < len; i++) {
            ds.v[i + B][0] = id[i + bl];
            ds.ans[i + B][1][1] = {seq[i + bl], seq[i + bl]};
        }
        for (int i = len; i < B; i++) {
            ds.v[i + B][0] = -1;
            ds.ans[i + B][1][1] = Info();
        }
        ds.build();

        h.assign(n + 1, 0);
        h[0] = B - len;
        for (int i = bl; i <= br; i++) h[id[i] + 1]++;
        for (int i = 0; i < n; i++) h[i + 1] += h[i];
    };

    vector<i64> ans(q);
    for (int l = 0, r; l < n; l = r + 1) {
        r = min(l + B, n) - 1;
        init(l, r);
        for (int i = 0; i < q; i++) {
            auto cur = ds.qry(h[L[i]] + 1, h[R[i] + 1]);
            ans[i] = max(ans[i] + cur.sum, cur.suf);
        }
    }

    for (int i = 0; i < q; i++) 
        qout << max(ans[i], 0LL) + pre[R[i] + 1] - pre[L[i]] << '\n';

    return 0;
}

::::