「LibreOJ Round #6」花团

    「LibreOJ Round #6」花团

    LOJ 534

    物品集合 SS 初始为空,按时间递增顺序依次给出 qq 次操作,操作如下:

    • 1 v w e:表示在 SS 中加入一个体积为 vv 价值为 ww 的物品,第 ee 次操作结束之后移除该物品。

    • 2 v:表示询问。你需要回答:

      1. 当前 SS 是否存在一个子集使得子集中物品体积和为 vv。
      2. 当前 SS 的所有物品体积和为 vv 的子集中,价值和最大是多少(空集的价值和为 00)。

    本题强制在线。

    数据范围:1≤q≤150001 \leq q \leq 15000,1≤vi≤150001 \leq v_i \leq 15000,0≤wi≤150000 \leq w_i \leq 15000。

    时空限制:33s / 256256MiB。

    Solution

    离线

    容易想到线段树分治。

    套用线段树分治的流程,就可以做到 O(qvlog⁡q)\mathcal{O}(qv \log q) 的时空复杂度。

    trick:对经过节点的深度加以区分,设 f[dep][] 表示处理到第 dep\text{dep} 层的某一个节点的 dp 数组。

    • 在节点 pp 做 dp 的时候,直接在 f[dep][] 中进行 dp。
    • 向节点 pp 的左右儿子进行递归前,花费 O(v)\mathcal{O}(v) 的时间将 f[dep][] 的信息传递给 f[dep + 1][]。

    本质上是用了一个栈维护了根节点至当前节点路径上,所有点的 dp 数组。空间复杂度降至 O(vlog⁡q)\mathcal{O}(v \log q)。

    在线

    还是可以考虑线段树分治。

    依旧套用线段树分治的流程,将所有插入 / 询问放在线段树的叶子上处理。

    对于查询,直接使用 dp 数组的信息回答询问即可;
    对于询问,由于物品恰好是在当前时间生效的,则其影响到的区间一定是我们还未访问过的,将该操作放入线段树即可。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector> 
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 100100;
    const int INF = 1e9;
    
    int Q, m, T;
    
    int lastans;
    
    vector< pair<int, int> > art[N * 4];
    
    void insert(int p, int l, int r, int s, int e, pair<int, int> x) {
        if (s <= l && r <= e) {
            art[p].push_back(x);
            return;
        }
        int mid = (l + r) >> 1;
        if (s <= mid)
            insert(p * 2, l, mid, s, e, x);
        if (mid < e)
            insert(p * 2 + 1, mid + 1, r, s, e, x);
    }
    
    int f[20][N];
    
    void solve(int p, int l, int r, int dep) {
        for (int j = 0; j < (int)art[p].size(); j ++) {
            pair<int, int> x = art[p][j];
            int w = x.first, v = x.second;
            for (int i = m; i >= w; i --)
                f[dep][i] = max(f[dep][i], f[dep][i - w] + v);
        }
    
        if (l == r) {
            int opt = read();
            int d = lastans * T;
    
            switch (opt) {
                case 1: {
                    int w = read() - d, v = read() - d, e = read() - d;
                    insert(1, 1, Q, l + 1, e, make_pair(w, v));
                    break;
                }
    
                case 2: {
                    int v = read() - d;
                    int X, Y;
    
                    if (f[dep][v] > -INF) X = 1, Y = f[dep][v];
                    else X = Y = 0;
    
                    printf("%d %d\n", X, Y);
                    lastans = X ^ Y;
    
                    break;
                }
            }
        } else {
            int mid = (l + r) >> 1;
    
            for (int i = 0; i <= m; i ++) f[dep + 1][i] = f[dep][i];
            solve(p * 2, l, mid, dep + 1);
    
            for (int i = 0; i <= m; i ++) f[dep + 1][i] = f[dep][i];
            solve(p * 2 + 1, mid + 1, r, dep + 1);
        }
    }
    
    int main() {
        Q = read(), m = read(), T = read();
    
        f[0][0] = 0;
        for (int i = 1; i <= m; i ++) f[0][i] = -INF * 2;
    
        solve(1, 1, Q, 0);
    
        return 0;
    }