题解「SFCOI-3」进行一个走的行

Leasier · 2023-07-17 23:53:28 · 题解

Subtask 1

暴力模拟题意即可。时间复杂度为 O(nm)。

Subtask 2

考虑差分，将询问 Q(l, r, x) 转化为 Q(1, r, x + sum_{l - 1}) - Q(1, l - 1, x + sum_{l - 1})，其中 sum_i = \displaystyle\sum_{j = 1}^i [r_j = -1] l_j。

把所有前缀询问的 x 抓出来离散化，BIT 维护区间加、单点求值即可。时间复杂度为 O((n + m) \log m)。

Subtask 3

依然差分，现在我们只需要考虑处理前缀问题。

考虑一个比较暴力的做法：

维护一棵 Treap，每个节点上记录到达 1 前代币数量为 x 时现在代币数量为 y，当前愉悦值为 z。
每遇到一个 (l_i, v_i)，首先把整个 Treap 拿来 split 成 [1, l_i], (l_i, 2l_i], (2l_i, +\infty) 三段。
给第三段打上其 y 减去 l_i 的标记，给第二、三段打上其 z 加上 v_i 的标记。
暴力取出第二段中的数，给其 y 减去 l_i 后插入第一段。
合并第一、三段。

下面我们来证明它的时间复杂度是正确的：

在某一次操作 l_i 中，只有 x \in (l_i, 2l_i] 者可能对时间复杂度产生比一般平衡树操作多的贡献。
而 x - l_i \leq \frac{x}{2}，则每产生一次这样的贡献后 x 大小至少减半。
设 w = 10^9，则任意 x 至多产生 O(\log w) 次贡献。

时间复杂度为 O(n \log m + m \log m \log w)。

Subtask 4

~~可能有依赖值域的做法，但是我不太清楚。~~

Subtask 5

如果没想到差分，可以考虑分块维护 Subtask 7 的做法。离线下来逐块处理即可。

设块长为 S，则时间复杂度为 O(mS + n \log m + \frac{nm \log m \log w}{S})，取 S = \sqrt{n \log m \log w} 取最优时间复杂度为 O(m \sqrt{n \log m \log w} + n \log m)。

Subtask 6

~~可能有依赖随机性的做法，但是我不太清楚。~~

Subtask 7

在 Subtask 3 的基础上加上区间加操作即可。

时间复杂度同 Subtask 3，为 O(n \log m + m \log m \log w)。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct Query_tag {
    int id;
    int r;
    ll x;
    int type;
    Query_tag(){}
    Query_tag(int id_, int r_, ll x_, int type_){
        id = id_;
        r = r_;
        x = x_;
        type = type_;
    }
} Query;

typedef struct {
    int father;
    int ls;
    int rs;
    ll sub;
    ll add;
    ll real_val;
    ll sum;
    int heap_val;
} Node;

int root, id = 0;
int l[200007], r[200007], v[200007], anc[200007];
ll sum[200007], a[200007], ans[200007];
Query query[400007];
Node tree[200007];

bool operator <(const Query a, const Query b){
    return a.r < b.r;
}

inline int read(){
    int sign = 1, ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') sign = -sign;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return sign * ans;
}

inline void pushdown(int x){
    int ls = tree[x].ls, rs = tree[x].rs;
    if (tree[x].sub != 0){
        tree[ls].sub += tree[x].sub;
        tree[rs].sub += tree[x].sub;
        tree[ls].real_val -= tree[x].sub;
        tree[rs].real_val -= tree[x].sub;
        tree[x].sub = 0;
    }
    if (tree[x].add != 0){
        tree[ls].add += tree[x].add;
        tree[rs].add += tree[x].add;
        tree[ls].sum += tree[x].add;
        tree[rs].sum += tree[x].add;
        tree[x].add = 0;
    }
}

inline void update(int x){
    int ls = tree[x].ls, rs = tree[x].rs;
    if (ls != 0) tree[ls].father = x;
    if (rs != 0) tree[rs].father = x;
}

void split(int x, int &y, int &z, ll val){
    if (x == 0){
        y = z = 0;
        return;
    }
    pushdown(x);
    if (tree[x].real_val <= val){
        y = x;
        split(tree[x].rs, tree[x].rs, z, val);
    } else {
        z = x;
        split(tree[x].ls, y, tree[x].ls, val);
    }
    update(x);
}

inline int new_node(ll x){
    int ans = ++id;
    tree[ans].real_val = x;
    tree[ans].heap_val = rand();
    return ans;
}

int merge(int x, int y){
    if (x == 0) return y;
    if (y == 0) return x;
    pushdown(x);
    pushdown(y);
    if (tree[x].heap_val < tree[y].heap_val){
        tree[x].rs = merge(tree[x].rs, y);
        update(x);
        return x;
    }
    tree[y].ls = merge(x, tree[y].ls);
    update(y);
    return y;
}

inline void insert1(ll x){
    int y, z;
    split(root, y, z, x);
    root = merge(y, merge(new_node(x), z));
    tree[root].father = 0;
}

inline void insert2(int &root, int x){
    int y, z;
    split(root, y, z, tree[x].real_val);
    root = merge(y, merge(x, z));
    tree[root].father = 0;
}

void dfs(int &root, int x){
    if (x == 0) return;
    pushdown(x);
    dfs(root, tree[x].ls);
    dfs(root, tree[x].rs);
    tree[x].father = tree[x].ls = tree[x].rs = 0;
    insert2(root, x);
}

inline void process(int x, int y){
    int u, v, w;
    split(root, u, v, x);
    tree[v].sub += x;
    tree[v].real_val -= x;
    tree[v].add += y;
    tree[v].sum += y;
    split(v, v, w, x);
    dfs(u, v);
    root = merge(u, w);
}

inline void add(int l, int r, int x){
    int y, z, w;
    split(root, y, z, l - 1);
    split(z, z, w, r);
    tree[z].add += x;
    tree[z].sum += x;
    root = merge(y, merge(z, w));
}

inline ll get_val(int x){
    int cnt = 0;
    for (register int i = x; i != 0; i = tree[i].father){
        anc[++cnt] = i;
    }
    for (register int i = cnt; i >= 1; i--){
        pushdown(anc[i]);
    }
    return tree[x].sum;
}

int main(){
    int n = read(), m = read(), k, q = 0;
    for (register int i = 1; i <= n; i++){
        l[i] = read();
        r[i] = read();
        v[i] = read();
        if (r[i] == -1){
            sum[i] = sum[i - 1] + l[i];
        } else {
            sum[i] = sum[i - 1];
        }
    }
    for (register int i = 1; i <= m; i++){
        int l = read(), r = read(), x = read();
        ll x_ = x + sum[l - 1];
        a[i] = x_;
        query[++q] = Query(i, r, x_, 1);
        if (l > 1) query[++q] = Query(i, l - 1, x_, -1);
    }
    sort(a + 1, a + m + 1);
    k = unique(a + 1, a + m + 1) - a - 1;
    for (register int i = 1; i <= k; i++){
        insert1(a[i]);
    }
    for (register int i = 1; i <= q; i++){
        query[i].x = lower_bound(a + 1, a + k + 1, query[i].x) - a;
    }
    sort(query + 1, query + q + 1);
    for (register int i = 1, j = 1; i <= n; i++){
        if (r[i] == -1){
            process(l[i], v[i]);
        } else {
            add(l[i], r[i], v[i]);
        }
        while (j <= q && query[j].r == i){
            ans[query[j].id] += query[j].type * get_val(query[j].x);
            j++;
        }
    }
    for (register int i = 1; i <= m; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

题解 「SFCOI-3」进行一个走的行