2018年第九届蓝桥杯省赛-H.日志统计

原题链接

题面

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 N 行。其中每一行的格式是：

ts id

表示在 ts 时刻编号 id 的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是"热帖"。

具体来说，如果存在某个时刻 T 满足该帖在 [T, T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是"热帖"。

给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

输入描述

输入格式：

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

其中，$1 \leq K \leq N \leq 10^5, 0 \leq ts \leq 10^5,0 \leq id \leq 10^5$。

输出描述

按从小到大的顺序输出热帖 id。每个 id 一行。

输入样例

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例

1
3

题解

前缀和，树状数组

首先，对每个不同的 id 进行分组，分组之后，对每个组别出现的时间进行排序，则排序后的数组为该 id 下从0时刻开始依次出现点赞的时刻 arr。要找到一个长度为 D 的时间段，满足其中出现的总的点赞次数大于等于 K，我们可以将 arr 中的每个时刻放到 [0, 100000] 这个区间的数组 b 中，b[i] 表示在 i 时刻出现的点赞次数，再累加其前缀和得到数组 s，则我们只要找到一个长度为 D 的区间，使得 s[i] - s[i - D] >= k ，即该 id 的日志为热帖。

对于上述的算法，（1）对每个组进行排序，（2）排序后计算每个时刻存在的点赞数，（3）再统计其前缀和，（4）最后从 [0, 100000] 这个区间中枚举找到满足条件的子区间。该其复杂度最坏情况下为为 $10^{10}$ 数量级，显然超时，需考虑优化。

我们可以将（2）（3）（4）三个步骤优化为一个循环，使用树状数组，边获取一个点赞时刻，就累加到树状数组中，并检测以当前时刻为结束区间的前 D 个时刻（前面不满D个时刻则从0开始）开始的区间出现的点赞数是否大于等于目标 K 即可。其时间复杂度最坏情况为 $10^6$ 数量级，能满足要求。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, d, k, tot, a[N], c[N], ans[N];
vector<int> id[N];

void add(int x, int y) {
    for (; x < N; x += x & -x) c[x] += y;
}

int get(int x) {
    int s = 0;
    for (; x; x -= x & -x) s += c[x];
    return s;
}

int main() {
    cin >> n >> d >> k;
    for (int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        id[y].push_back(x + 1);
    }

    for (int i = 0; i <= 100000; i++) {
        if (id[i].size() < k) continue;
        memset(c, 0, sizeof c);
        vector<int> &arr = id[i];
        sort(arr.begin(), arr.end());

        for (int j = 0; j < arr.size(); j++) {
            int t = arr[j];
            add(t, 1);
            if (get(t) - get(max(t - d, 0)) >= k) {
                ans[++tot] = i;
                break;
            }
        }
    }

    for (int i = 1; i <= tot; i++) printf("%d\n", ans[i]);

    return 0;
}