社团活动

https://www.matiji.net/exam/dohomework/8235/4

题干

小码弟正在组织社团活动。

社团活动一共有 $n$ 个项目，第 $i$ 个项目将于第 $l_i$ 天到第 $r_i$ 天进行。

社团中有 $m$ 个社员，第 $j$ 位社员将在第 $a$ 到第 $b$ 天有时间参加项目，一位社员每天可以参加多个项目。

小码弟想知道每位社员分别最多能完整完成几个项目。

思路

即给定 $n$ 个区间 $[l_i, r_i]$ ，$m$ 个区间 $[a_i, b_i]$，求每个 $[a_i, b_i]$ 包含的 $[l_i, r_i]$ 区间个数。

$n \leq 1e5, m \leq 1e5, r_i \leq 1e5, l_i \leq 1e5$ ，复杂度大概是 $O((n + m) log (n + m))$ 的形式。线性时间复杂度看起来不太可能，因此应当有 $log$ 项。 $log$ 项这里应该是线段树或者树状数组。这里用树状数组做。

对于每一个查询，将所有满足 $l_i \geq a_i$ 的项目放入树状数组，然后统计满足 $r_i \leq b_i$ 的项目个数。这里的放入是对右端点进行计数，后一步则是指区间求和。

这样会导致平方乘对数形式的复杂度。考虑先把项目和查询都按左端点排序，这样每次添加项目时，不需要遍历记录，只要从上次结束的项目继续添加即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 项目结构体，表示项目的起始时间 l 和结束时间 r
struct Project {
    int l, r;
};

// 查询结构体，表示社员可参加活动的时间区间 [a, b] 以及原始查询编号 id
struct Query {
    int a, b, id;
};

// 树状数组结构体（Fenwick Tree）的封装
struct fenw_tree {
    int n;                 // 数组大小
    vector<int> tree;      // 内部数组（从下标 1 开始使用）

    // 构造函数，初始化大小为 n 的树状数组，所有值初始为 0
    fenw_tree(int n) : n(n), tree(n + 1, 0) {}

    // 更新函数：将下标 idx 处的值加上 delta
    void update(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }

    // 前缀和查询：返回区间 [1, idx] 内的累加和
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    // 读入所有项目
    vector<Project> projects(n);
    for (int i = 0; i < n; i++) {
        cin >> projects[i].l >> projects[i].r;
    }

    // 读入所有查询
    vector<Query> queries(m);
    for (int i = 0; i < m; i++) {
        cin >> queries[i].a >> queries[i].b;
        queries[i].id = i;
    }

    // 将项目按 l 降序排序
    sort(projects.begin(), projects.end(), [](const Project &p1, const Project &p2) {
        return p1.l > p2.l;
    });

    // 将查询按 a 降序排序
    sort(queries.begin(), queries.end(), [](const Query &q1, const Query &q2) {
        return q1.a > q2.a;
    });

    // 天数的上界（题中规定最大天数为 100000）
    const int max_day = 100000;
    // 构造一个大小为 max_day 的树状数组（下标范围 [1, max_day]）
    fenw_tree bit(max_day);

    // answer 数组存储每个查询的答案
    vector<int> answer(m, 0);
    int proj_idx = 0;
    // 逐个处理查询
    // 对于每个查询 q，其要求项目必须满足 l >= q.a 且 r <= q.b
    // 先把所有满足 l >= q.a 的项目加入树状数组（以其 r 作为下标更新），
    // 然后对树状数组查询 [1, q.b] 的前缀和即可得到答案
    for (const auto &q : queries) {
        while (proj_idx < n && projects[proj_idx].l >= q.a) {
            // 在项目的结束时间 r 处加 1
            bit.update(projects[proj_idx].r, 1);
            proj_idx++;
        }
        // 查询 [1, q.b] 得到的就是 r <= q.b 的项目数
        answer[q.id] = bit.query(q.b);
    }

    // 按原始查询顺序输出答案
    for (int i = 0; i < m; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

这里把树状数组换成线段树效果一样。

模版

附上一份线段树和 Fenwick 树的模版。线段树用 zkw 的实现。

#include <vector>

using namespace std;


struct SegmentTree {
    int n;
    vector<int> data;
    SegmentTree(const vector<int> raw) {
        this->n = raw.size();
        this->data.assign(4 * this->n, 0);
        for(int i = 0; i < n; ++i) {
            data[i + n] = raw[i];
        }
        for(int i = n - 1; i > 0; --i) {
            data[i] = data[2 * i] + data[2 * i + 1];
        }
    }

    void update_to(int idx, int target) {
        data[idx + n] = target;
        for(int i = idx + n; i > 1; i /= 2) {
            data[i / 2] = data[i] + data[i + 1];
        }
    }

    void update_by(int idx, int delta) {
        data[idx + n] += delta;
        for(int i = idx + n; i > 1; i /= 2) {
            data[i / 2] += delta;
        }
    }

    int query(int l, int r) {
        int sum = 0;
        for(l += n, r += n; l <= r; l /= 2, r /= 2) {
            if(l % 2 == 1) {
                sum += data[l];
                ++l;
            }
            if(r % 2 == 0) {
                sum += data[r];
                --r;
            }
        }
        return sum;
    }
};

#include <vector>

using namespace std;;

inline int lowbit(int x) {
    return x & (-x);
}

struct Fenwick {
    vector<int> data;
    int n;

    Fenwick(const vector<int>& raw) {
        this->n = raw.size();
        this->data.resize(n + 1, 0);
        for(int i = 0; i < n; ++i) {
            this->data[i + 1] = raw[i];
        }
        for(int i = 1; i <= n; ++i) {
            int j = i + lowbit(i);
            if(j <= n) {
                this->data[j] += this->data[i];
            }
        }
    }

    void update(int idx, int delta) {
        for(int i = idx; i <= n; i += lowbit(i)) {
            this->data[i] += delta;
        }
    }

    int query(int idx) {
        ++idx;
        int sum = 0;
        for(int i = idx; i > 0; i -= lowbit(i)) {
            sum += this->data[i];
        }
        return sum;
    }
};