题解：客栈住宿方案计数（前缀和 + 哈希计数）

一、解题核心思路

本题的核心是 统计满足两个条件的客栈对数量：

1. 两家客栈色调相同；
2. 两家客栈之间（含自身）存在至少一家咖啡店的最低消费 ≤ $p$。

直接暴力枚举所有同色调客栈对（$O(n^2)$）会超时，需通过 前缀和 + 哈希计数 优化，核心思路如下：

1. 维护「最近的合法咖啡店位置」：遍历客栈时，记录最后一次出现最低消费 ≤ $p$ 的位置 last_valid，表示当前客栈左侧最近的合法咖啡店位置。
2. 哈希计数统计同色调客栈：用数组 cnt 记录每种色调的客栈总数，用数组 sum 记录每种色调的客栈位置之和（用于快速计算合法对数）。
3. 分情况计算合法对数：
   • 若当前客栈的咖啡店最低消费 ≤ $p$：则当前客栈与所有同色调的前序客栈都构成合法对（因为中间有当前客栈的合法咖啡店），对数为 cnt[color]。
   • 若当前客栈的咖啡店最低消费 > $p$：则仅当前客栈与「位置 ≥ last_valid」的同色调前序客栈构成合法对（因为中间需有之前的合法咖啡店），通过前缀和快速计算该区间的同色调客栈数。

二、关键优化细节

1. 前缀和数组设计：由于 $n$ 可达 $2 \times 10^6$，直接维护每种色调的位置前缀和数组会超内存，因此改用「动态维护总和」的方式：

   • cnt[color]：当前色调 color 的客栈总数；
   • sum[color]：当前色调 color 的所有客栈位置之和；
   • 当遇到新的合法位置 last_valid 时，之前的同色调客栈中，位置 < last_valid 的部分不再对后续客栈构成合法对，因此需要重置 cnt[color] 和 sum[color]（仅保留位置 ≥ last_valid 的客栈）。

2. 时间复杂度优化：遍历所有客栈仅需 $O(n)$，每种色调的操作均为 $O(1)$，整体时间复杂度为 $O(n)$，适配 $n \leq 2 \times 10^6$ 的数据范围。

三、具体解题步骤

1. 初始化变量：

   • last_valid = -1：记录最近的合法咖啡店位置（初始为 -1，表示无合法咖啡店）；
   • cnt[k] = {0}：记录每种色调的客栈总数；
   • sum[k] = {0}：记录每种色调的客栈位置之和；
   • ans = 0：记录合法方案总数。

2. 遍历所有客栈（索引从 $1$ 到 $n$）： a. 读取当前客栈的色调 color 和最低消费 cost。 b. 更新 last_valid：若 cost ≤ p，则 last_valid = i（当前位置为合法位置）。 c. 计算当前客栈贡献的合法对数：

   • 若 cost ≤ p：
     • 贡献对数为 cnt[color]（所有同色调前序客栈都合法）；
     • ans += cnt[color]；
   • 若 cost > p：
     • 若 last_valid == -1：无合法对数（无任何合法咖啡店）；
     • 否则：贡献对数为 cnt[color] - (sum[color] < last_valid ? 0 : ...) → 需通过之前的总和快速计算，此处优化为：当 last_valid 更新时，重置 cnt 和 sum，因此当前 cnt[color] 已仅包含位置 ≥ last_valid 的客栈，直接贡献 cnt[color]。 d. 更新 cnt[color] 和 sum[color]：
   • 若 cost ≤ p：重置当前色调的 cnt[color] = 0、sum[color] = 0（因为后续客栈与当前客栈构成合法对时，无需考虑之前的旧客栈）；
   • cnt[color] += 1；
   • sum[color] += i。

3. 输出结果：遍历结束后，ans 即为合法方案总数。

四、完整代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_K = 1e4 + 5;
const int MAX_N = 2e6 + 5;

int cnt[MAX_K];   // 每种色调的客栈数量
long long sum[MAX_K]; // 每种色调的客栈位置之和（仅保留≥last_valid的）
long long ans = 0;
int last_valid = -1; // 最近的合法咖啡店位置（cost ≤ p）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, p;
    cin >> n >> k >> p;

    memset(cnt, 0, sizeof(cnt));
    memset(sum, 0, sizeof(sum));

    for (int i = 1; i <= n; ++i) {
        int color, cost;
        cin >> color >> cost;

        // 更新最近的合法位置
        if (cost <= p) {
            last_valid = i;
        }

        // 计算当前客栈贡献的合法对数
        if (last_valid != -1) {
            ans += cnt[color];
        }

        // 若当前是合法位置，重置该色调的计数（后续客栈与当前客栈配对时，无需考虑之前的旧客栈）
        if (cost <= p) {
            cnt[color] = 0;
            sum[color] = 0;
        }

        // 更新该色调的计数和位置和
        cnt[color]++;
        sum[color] += i;
    }

    cout << ans << endl;

    return 0;
}

五、代码解释

1. 变量初始化：cnt 和 sum 数组分别记录每种色调的客栈数量和位置之和，last_valid 记录最近的合法咖啡店位置。
2. 遍历客栈：
   • 每次读取客栈信息后，更新 last_valid（若当前客栈消费合法）。
   • 若存在合法咖啡店（last_valid != -1），则当前客栈与所有同色调的前序客栈（已记录在 cnt[color] 中）构成合法对，累加 cnt[color] 到 ans。
   • 若当前客栈消费合法，重置该色调的 cnt 和 sum（因为后续客栈与当前客栈配对时，中间有当前合法咖啡店，无需考虑更早的客栈）。
   • 最后更新当前色调的 cnt 和 sum，纳入当前客栈。
3. 输出结果：ans 即为所有合法的住宿方案数。

六、复杂度分析

• 时间复杂度：$O(n)$。遍历所有客栈仅需一次，每种色调的操作均为 $O(1)$，无嵌套循环。
• 空间复杂度：$O(k)$。cnt 和 sum 数组大小为 $k$（$k \leq 1e4$），空间开销可控。

该代码通过动态维护合法位置和同色调计数，高效解决了大规模数据下的计数问题，避免了暴力枚举的超时风险。