题解：P8512 [Ynoi Easy Round 2021] TEST_152

· · 题解

solution

先考虑特殊的，假设每一组询问 (L,R)，满足 L = 1 那么问题简化为依次执行操作序列的第 1,2,\cdots,R 项所对应的操作，此时答案为 \sum^{m}_{i=1}C_i。

但是对于询问 (L,R)，不能直接用 (1,R) 与 (1,L-1) 对应的答案相见，因为可能会覆盖之前的操作，此处应该可以想到 ODT，离线，将询问挂在 r 上扫描线，对于一段，其操作序列中的顺序是第 t 个，权值为 v，区间长度为 l，对于 t 如果被覆盖，其对后续的贡献为 -l\times v，记 t 的对当前贡献为 a_t，那么显然答案是 \sum^{n}_{i=L}a_i。

时间复杂度分析

ODT O(n\log n)，询问总共需要 O(n\log n)，n, m, q 同阶，此处不区分。

code

感觉代码整体很板。 ::::info[使用了AI工具提升代码可读性]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

namespace FastIO {
    const int BUFFER_SIZE = 1 << 20;
    char inbuf[BUFFER_SIZE], outbuf[BUFFER_SIZE];
    char *pin = inbuf, *pin_end = inbuf;
    int outpos = 0;

    inline char getchar() {
        if (pin == pin_end) {
            pin = inbuf;
            pin_end = inbuf + fread(inbuf, 1, BUFFER_SIZE, stdin);
            if (pin == pin_end) return EOF;
        }
        return *pin++;
    }

    template <typename T>
    inline T read() {
        T x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + (ch - '0');
            ch = getchar();
        }
        return x * f;
    }

    template <typename T>
    inline void write(T x, char end_char = '\n') {
        if (outpos >= BUFFER_SIZE - 32) {
            fwrite(outbuf, 1, outpos, stdout);
            outpos = 0;
        }
        if (x < 0) {
            outbuf[outpos++] = '-';
            x = -x;
        }
        char temp[64];
        int len = 0;
        do {
            temp[len++] = x % 10 + '0';
            x /= 10;
        } while (x);
        while (len--) {
            outbuf[outpos++] = temp[len];
        }
        outbuf[outpos++] = end_char;
    }

    inline void flush() {
        if (outpos) {
            fwrite(outbuf, 1, outpos, stdout);
            outpos = 0;
        }
    }
} using namespace FastIO;

const int MAX_N = 5e5 + 10;

// 线段信息结构体
struct Segment {
    int left, right;    // 线段左右端点
    int timestamp;      // 时间戳（赋值时间）
    int value;          // 线段的值

    Segment() : left(0), right(0), timestamp(0), value(0) {}
    Segment(int l, int r, int t, int v) : left(l), right(r), timestamp(t), value(v) {}

    // 按左端点排序
    bool operator < (const Segment &other) const {
        if (left != other.left) return left < other.left;
        if (right != other.right) return right < other.right;
        if (timestamp != other.timestamp) return timestamp < other.timestamp;
        return value < other.value;
    }
};

// 查询结构体
struct QueryInfo {
    int left_bound;     // 查询左边界
    int query_id;       // 查询ID

    QueryInfo(int l, int id) : left_bound(l), query_id(id) {}
};

int n, m, q;
int segment_left[MAX_N], segment_right[MAX_N], segment_value[MAX_N];
int answer[MAX_N];
vector<QueryInfo> queries_by_right[MAX_N];

// 珂朵莉树（ODT）
set<Segment> odt_set;

// 树状数组（用于区间查询）
int fenwick_tree[MAX_N];

// 树状数组：单点更新
void update_fenwick(int position, int delta) {
    for (; position > 0; position -= position & -position) {
        fenwick_tree[position] += delta;
    }
}

// 树状数组：前缀和查询
int query_fenwick(int position) {
    int result = 0;
    for (; position <= n; position += position & -position) {
        result += fenwick_tree[position];
    }
    return result;
}

// ODT核心操作：在指定位置分割线段
set<Segment>::iterator split_odt(int split_position) {
    auto iter = odt_set.lower_bound(Segment(split_position, 0, 0, 0));
    if (iter != odt_set.end() && iter->left == split_position) {
        return iter;
    }

    iter--;
    Segment original_segment = *iter;
    odt_set.erase(iter);

    // 分割为两个线段
    odt_set.insert(Segment(original_segment.left, split_position - 1, 
                         original_segment.timestamp, original_segment.value));

    auto result = odt_set.insert(Segment(split_position, original_segment.right,
                                      original_segment.timestamp, original_segment.value));
    return result.first;
}

// ODT核心操作：区间赋值
void assign_odt(int assign_left, int assign_right, int timestamp, int value) {
    // 分割出操作区间
    auto right_iter = split_odt(assign_right + 1);
    auto left_iter = split_odt(assign_left);

    // 删除原有线段的影响
    for (auto iter = left_iter; iter != right_iter; ++iter) {
        const Segment &seg = *iter;
        int segment_length = seg.right - seg.left + 1;
        update_fenwick(seg.timestamp, -segment_length * seg.value);
    }

    // 删除旧线段，插入新线段
    odt_set.erase(left_iter, right_iter);
    int new_length = assign_right - assign_left + 1;
    update_fenwick(timestamp, new_length * value);
    odt_set.insert(Segment(assign_left, assign_right, timestamp, value));
}

signed main() {
    // 读取输入
    n = read<int>(), m = read<int>(), q = read<int>();

    for (int i = 1; i <= n; i++) {
        segment_left[i] = read<int>();
        segment_right[i] = read<int>();
        segment_value[i] = read<int>();
    }

    // 存储查询
    for (int i = 1; i <= q; i++) {
        int query_left = read<int>(), query_right = read<int>();
        queries_by_right[query_right].emplace_back(query_left, i);
    }

    // 初始化ODT：整个区间初始值为0，时间戳为1
    odt_set.insert(Segment(1, m, 1, 0));

    // 处理每个时间点的操作
    for (int current_time = 1; current_time <= n; current_time++) {
        // 执行区间赋值操作
        assign_odt(segment_left[current_time], segment_right[current_time], 
                  current_time, segment_value[current_time]);

        // 处理当前时间点的所有查询
        for (const auto &query_info : queries_by_right[current_time]) {
            int prefix_sum = query_fenwick(query_info.left_bound);
            answer[query_info.query_id] = prefix_sum;
        }
    }

    // 输出所有查询结果
    for (int i = 1; i <= q; i++) {
        write(answer[i]);
    }

    flush();
    return 0;
}

::::