F - Apples

Problem Statement

There are apple trees lined up on a number line, and $N$ apples fall from the trees.
Specifically, for each $1\leq i\leq N$, an apple falls at coordinate $X_i$ at time $T_i$.

Takahashi has a basket with durability $D$ and length $W$, and he can take the following action exactly once.

Choose positive integers $S$ and $L$. He sets up the basket to cover the range $L-0.5\leq x\leq L+W-0.5$ at time $S-0.5$, and retrieves it at time $S+D-0.5$. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

$1 \leq N\leq 2\times 10^5$
$1 \leq D\leq 2\times 10^5$
$1 \leq W\leq 2\times 10^5$
$1 \leq T_i\leq 2\times 10^5$
$1 \leq X_i\leq 2\times 10^5$
All pairs $(T_i,X_i)$ are different.
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$ $W$

$T_1$ $X_1$

$T_2$ $X_2$

$\vdots$

$T_N$ $X_N$

Output

Print the maximum number of apples that Takahashi can get.

Sample Input 1

Sample Output 1

If Takahashi chooses $S=3$ and $L=2$, he will set up the basket to cover the range $1.5\leq x\leq 4.5$ from time $2.5$ to $6.5$. Then, he gets the following five apples:

The apple that falls at coordinate $X_2=4$ at time $T_2=3$
The apple that falls at coordinate $X_3=4$ at time $T_3=6$
The apple that falls at coordinate $X_4=2$ at time $T_4=5$
The apple that falls at coordinate $X_5=2$ at time $T_5=4$
The apple that falls at coordinate $X_6=3$ at time $T_6=4$

There is no way to get six or more apples, so print $5$.

解题思路

把每个苹果的参数 $(T_i, X_i)$ 看作是平面坐标系上的点，那么问题就变成了，用一个长为 $D$ 宽为 $W$ 且四边平行于坐标轴的矩形，最多能覆盖多少个点。这题最关键是能想到反过来统计每个点能对那些位置的矩阵有贡献。把矩形的左下角当作关键点，那么如果点 $(T_i, X_i)$ 能被矩形覆盖，则矩形左下角的坐标 $(t, x)$ 的范围就要满足$$\begin{cases} t \leq T_i \leq t + D - 1 \\ x \leq X_i \leq x + W - 1 \end{cases} \longrightarrow \begin{cases} T_i - D + 1 \leq t \leq T_i \\ X_i - W + 1 \leq x \leq X_i \end{cases}$$

对这个范围内的点都加上 $1$，表示如果选择矩阵的左下角在这个范围内，则点 $(T_i, X_i)$ 会有一个贡献。可以知道这个范围内的所有点本质上会组成一个矩形，对一个点统计就相当于选择这个范围构成的矩形来覆盖平面。那么对 $n$ 个点都统计后，平面上就会有 $n$ 个矩形（可能会有重叠），找到被覆盖次数最多的点作为矩形的左下角，则该矩形就能覆盖最多的点了。

为此可以用扫描线来处理，用线段树来维护纵坐标也就是 $x$ 被覆盖次数的最大值，修改操作就只有区间加。用线段树优化扫描线可以参考这篇博客。

AC 代码如下，时间复杂度为 $O(n \log{A})$：

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;

struct Seg {
    int x, y1, y2, c;
}p[N];
struct Node {
    int l, r, mx, add;
}tr[N * 4];

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, 0, 0};
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u] = {l, r, 0, 0};
    }
}

void pushdown(int u) {
    if (tr[u].add) {
        tr[u << 1].mx += tr[u].add;
        tr[u << 1].add += tr[u].add;
        tr[u << 1 | 1].mx += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add;
        tr[u].add = 0;
    }
}

void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].mx += c;
        tr[u].add += c;
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, c);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
        tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
    }
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        p[i << 1] = {max(1, x - m + 1), max(1, y - k + 1), y, 1};
        p[i << 1 | 1] = {x, max(1, y - k + 1), y, -1};
    }
    sort(p, p + 2 * n, [&](Seg &a, Seg &b) {
        if (a.x != b.x) return a.x < b.x;
        return a.c > b.c;    // 如果扫描线重叠，那么要保证加操作在减操作前面
    });
    build(1, 1, N - 1);
    int ret = 0;
    for (int i = 0; i < n << 1; i++) {
        modify(1, p[i].y1, p[i].y2, p[i].c);
        ret = max(ret, tr[1].mx);
    }
    printf("%d", ret);
    
    return 0;
}

上面的做法是参考 dreamoon 大佬的。下面再给出我之前的做法。

由于需要同时满足两个约束条件，不妨把其中一个固定，即对苹果按照 $T_i$ 从小到大排序，当枚举到第 $i$ 个苹果并作为矩形的右边界时，则最靠左能选到的苹果 $j$ 要满足 $T_j \geq T_i - D + 1$，这个可以用双指针来维护。接下来只需考虑另外一个条件，即长度为 $W$ 的线段最多能覆盖多少个这些苹果的 $X_i$。

与上面的思想一样，考虑每个点对哪些线段有贡献，把线段的左端点作为关键点，那么 $X_i$ 能被左端点在 $[X_i - W + 1, X_i]$ 且长度为 $W$ 的线段覆盖，对这个范围内的点加 $1$。因此可以线段树来维护某个区间的最大值，修改操作只有区间加。

AC 代码如下，时间复杂度为 $O(n \log{A})$：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int a[N], b[N], p[N];
struct Node {
    int l, r, add, mx;
}tr[N * 4];

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, 0, 0};
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u] = {l, r, 0, 0};
    }
}

void pushdown(int u) {
    if (tr[u].add) {
        tr[u << 1].mx += tr[u].add;
        tr[u << 1].add += tr[u].add;
        tr[u << 1 | 1].mx += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add;
        tr[u].add = 0;
    }
}

void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].mx += c;
        tr[u].add += c;
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, c);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
        tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
    }
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", a + i, b + i);
        p[i] = i;
    }
    sort(p + 1, p + n + 1, [&](int i, int j) {
        return a[i] < a[j];
    });
    build(1, 1, N - 1);
    int ret = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        modify(1, max(1, b[p[i]] - k + 1), b[p[i]], 1);
        while (a[p[i]] - a[p[j]] + 1 > m) {
            modify(1, max(1, b[p[j]] - k + 1), b[p[j]], -1);
            j++;
        }
        ret = max(ret, tr[1].mx);
    }
    printf("%d", ret);
    
    return 0;
}