题解：AtCoder AT_awc0082_d Corridor Doors and Hit Points

【题目来源】

AtCoder：D - Corridor Doors and Hit Points

【题目描述】

There is a corridor consisting of \(L\) rooms arranged in a horizontal row. The rooms are numbered from \(0\) to \(L - 1\) from left to right.

There is a door between each pair of adjacent rooms. Specifically, for each integer \(x\) satisfying \(1 \leq x \leq L - 1\), there is door \(x\) between room \(x - 1\) and room \(x\). Both ends of the corridor (the left side of room \(0\) and the right side of room \(L-1\)) are outer walls and cannot be passed through.

This corridor has \(N\) types of security patterns configured. Security pattern \(i\) has modulus \(A_i\), initial value \(R_i\), and time coefficient \(V_i\). At integer time \(t\), if door \(x\) (\(1 \leq x \leq L - 1\)) satisfies

\(x \equiv R_i + V_i \cdot t \pmod{A_i}\)

then security pattern \(i\) places \(1\) lock on that door. Multiple security patterns may place locks on the same door at the same time.

The weight of door \(x\) at time \(t\) is defined as the total number of locks placed on that door at time \(t\).

You are given \(Q\) queries. In query \(j\), Takahashi is in room \(S_j\) at time \(T_j\). Fix the state of the locks at time \(T_j\) (without considering changes over time) and consider the following.

Takahashi's stamina is \(P_j\). For Takahashi to reach room \(c\) from room \(S_j\), he must pass through all doors between \(S_j\) and \(c\) in order. If the total weight of the doors he passes through is at most \(P_j\), then Takahashi can reach room \(c\).

For each query, find the number of rooms Takahashi can reach. Note that room \(S_j\) where Takahashi starts is also counted as a reachable room.

有一条走廊，由 \(L\) 个房间水平排列组成。房间从左到右编号为 \(0\) 到 \(L - 1\)。

每对相邻房间之间有一扇门。具体来说，对于每个满足 \(1 \leq x \leq L - 1\) 的整数 \(x\)，在房间 \(x - 1\) 和房间 \(x\) 之间有门 \(x\)。走廊的两端（房间 \(0\) 的左侧和房间 \(L-1\) 的右侧）是外墙，无法通过。

这条走廊配置了 \(N\) 种安全模式。安全模式 \(i\) 具有模数 \(A_i\)、初始值 \(R_i\) 和时间系数 \(V_i\)。在整数时刻 \(t\)，如果门 \(x\)（\(1 \leq x \leq L - 1\)）满足

\(x \equiv R_i + V_i \cdot t \pmod{A_i}\)

则安全模式 \(i\) 在该门上放置 \(1\) 把锁。多个安全模式可以在同一时刻在同一扇门上放置锁。

门 \(x\) 在时刻 \(t\) 的权重定义为该门在时刻 \(t\) 上放置的锁的总数。

给定 \(Q\) 个查询。在查询 \(j\) 中，高桥在时刻 \(T_j\) 位于房间 \(S_j\)。固定时刻 \(T_j\) 的锁状态（不考虑随时间变化），考虑以下情况。

高桥的体力为 \(P_j\)。为了让高桥从房间 \(S_j\) 到达房间 \(c\)，他必须按顺序通过 \(S_j\) 和 \(c\) 之间的所有门。如果他通过的门的权重总和不超过 \(P_j\)，则高桥可以到达房间 \(c\)。

对于每个查询，求高桥可以到达的房间数量。注意，高桥起始的房间 \(S_j\) 也计入可到达的房间。

【输入】

\(N\) \(L\) \(Q\)
\(A_1\) \(R_1\) \(V_1\)
\(A_2\) \(R_2\) \(V_2\)
:
\(A_N\) \(R_N\) \(V_N\)
\(T_1\) \(S_1\) \(P_1\)
\(T_2\) \(S_2\) \(P_2\)
:
\(T_Q\) \(S_Q\) \(P_Q\)

• The first line contains \(N\) representing the number of security patterns, \(L\) representing the number of rooms, and \(Q\) representing the number of queries, separated by spaces.
• The following \(N\) lines give the security pattern information.
• The \((1 + i)\)-th line contains the modulus \(A_i\), initial value \(R_i\), and time coefficient \(V_i\) of pattern \(i\), separated by spaces.
• The following \(Q\) lines give the query information.
• The \((1 + N + j)\)-th line contains the time \(T_j\), the room number \(S_j\) where Takahashi is, and the stamina \(P_j\) for query \(j\), separated by spaces.

【输出】

Output \(Q\) lines.

On the \(j\)-th line, output the number of rooms Takahashi can reach for query \(j\).

【输入样例】

2 6 4
2 0 1
3 1 0
0 0 0
0 2 2
1 3 1
2 5 10

【输出样例】

1
6
4
6

【核心思想】

1. 问题分析：给定 \(L\) 个房间和 \(L-1\) 扇门，\(N\) 种安全模式会在特定时刻给特定门加锁。对于每个查询 \((T_j, S_j, P_j)\)，需要计算从房间 \(S_j\) 出发，在体力 \(P_j\) 限制下（通过门的锁总数 \(\leq P_j\)），能到达的房间数量。这是一个二分查找 + 前缀和问题，需要分别向左右两个方向扩展。

2. 算法选择：

   • 数学计数：对于每种安全模式 \((A_i, R_i, V_i)\)，计算时刻 \(t\) 时门 \(x\) 满足 \(x \equiv R_i + V_i \cdot t \pmod{A_i}\) 的锁数量
   • 前缀和优化：通过 countLocks() 函数计算 \(\leq idx\) 的锁数量，区间锁数量 = 前缀和相减
   • 两次二分查找：分别二分查找能到达的最左边界和最右边界

3. 关键步骤：

   • 锁位置计算：对于安全模式 \((a, r, v)\) 在时刻 \(t\)，第一个锁位置为 \(first = ((r \bmod a) + (v \bmod a) \cdot (t \bmod a)) \bmod a\)，若 \(first = 0\) 则修正为 \(a\)
   • 前缀和计数：countLocks(a, r, v, t, idx) 计算 \(\leq idx\) 的锁数量，等差数列公式：\(\lfloor \frac{idx - first}{a} \rfloor + 1\)
   • 区间锁数量：countRange(l, r, t) 遍历 \(N\) 种模式，累加每种模式在区间 \([l, r]\) 的锁数量
   • 向左二分（findLeft）：
     • 在 \([0, S_j]\) 范围内二分，找最远的左边界 \(l\) 使得 \(\text{countRange}(l+1, S_j, T_j) \leq P_j\)
     • 若体力足够则尝试更左（\(r = mid\)），否则往右移动（\(l = mid + 1\)）
     • 返回向左能到达的房间数 \(S_j - l + 1\)
   • 向右二分（findRight）：
     • 在 \([S_j, L-1]\) 范围内二分，找最远的右边界 \(r\) 使得 \(\text{countRange}(S_j+1, r, T_j) \leq P_j\)
     • 若体力足够则尝试更右（\(l = mid\)），否则往左移动（\(r = mid - 1\)）
     • 返回向右能到达的房间数 \(r - S_j + 1\)
   • 合并答案：总房间数 = 向左房间数 + 向右房间数 - 1（起点 \(S_j\) 被重复计算）

4. 时间/空间复杂度：

   • 时间复杂度：\(O(Q \cdot N \cdot \log L)\)，每次查询进行两次二分，每次二分需要 \(O(N)\) 计算区间锁数量
   • 空间复杂度：\(O(N)\)，存储 \(N\) 种安全模式的参数

5. 二分查找与前缀和的核心思想：

   • 问题分解：将二维问题（左右扩展）分解为两个一维二分查找问题
   • 前缀和优化：通过等差数列公式 \(O(1)\) 计算单种模式的锁数量，避免枚举每个门
   • 二分判定：利用单调性（越往外扩展，锁总数单调不减），二分查找最远可达边界
   • 边界处理：向左查找用下取整 \(mid = (l + r) >> 1\)，向右查找用上取整 \(mid = (l + r + 1) >> 1\)，避免死循环
   • 适用于区间查询、范围判定、最远可达边界等场景

【算法标签】

整数二分

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;
int n, L, Q;  // n: 锁的数量，L: 门的数量，Q: 查询次数
struct Lock
{int a, r, v;  // 锁的参数
} locks[N];
// 计算安全模式 (a, r, v) 在时刻 t 时，门编号 <= idx 的锁的数量
int countLocks(int a, int r, int v, int t, int idx)
{int first = ((r % a) + (v % a) * (t % a) % a) % a;  // 计算第一个锁的位置if (first == 0)  // 如果余数为0first = a;  // 修正为aif (idx < first)  // 如果idx小于第一个锁的位置return 0;return (idx - first) / a + 1;  // 计算锁的数量
}
// 计算区间 [l, r] 内所有锁的总数
int countRange(int l, int r, int t)
{if (l > r)  // 无效区间return 0;int sum = 0;  // 锁的总数for (int i = 1; i <= n; i++)  // 遍历所有锁{sum += countLocks(locks[i].a, locks[i].r, locks[i].v, t, r)- countLocks(locks[i].a, locks[i].r, locks[i].v, t, l - 1);  // 前缀和}return sum;  // 返回总数
}
// 向左扩展，找最远的左边界
// 返回从 s 出发向左能到达的房间数量（包含 s）
int findLeft(int s, int p, int t)
{int l = 0, r = s;  // 二分查找边界while (l < r)  // 二分查找{int mid = (l + r) >> 1;  // 计算中点int cost = countRange(mid + 1, s, t);  // 计算从mid到s的锁数量if (cost <= p)  // 如果体力足够{r = mid;  // 尝试更左的位置}else{l = mid + 1;  // 需要往右移动}}return s - l + 1;  // 返回能到达的房间数
}
// 向右扩展，找最远的右边界
// 返回从 s 出发向右能到达的房间数量（包含 s）
int findRight(int s, int p, int t)
{int l = s, r = L - 1;  // 二分查找边界while (l < r)  // 二分查找{int mid = (l + r + 1) >> 1;  // 计算中点int cost = countRange(s + 1, mid, t);  // 计算从s到mid的锁数量if (cost <= p)  // 如果体力足够{l = mid;  // 尝试更右的位置}else{r = mid - 1;  // 需要往左移动}}return l - s + 1;  // 返回能到达的房间数
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> L >> Q;  // 输入锁的数量、门的数量和查询次数for (int i = 1; i <= n; i++)  // 输入每个锁的参数{cin >> locks[i].a >> locks[i].r >> locks[i].v;}while (Q--)  // 处理每个查询{int t, s, p;  // 时间、起点、体力cin >> t >> s >> p;  // 输入查询参数int leftCnt = findLeft(s, p, t);  // 向左能到达的房间数int rightCnt = findRight(s, p, t);  // 向右能到达的房间数cout << leftCnt + rightCnt - 1 << endl;  // 输出总房间数}return 0;
}

【运行结果】

2 6 4
2 0 1
3 1 0
0 0 0
1
0 2 2
6
1 3 1
4
2 5 10
6