思路与算法

按顺序扫描酒店，每色保存此前总数total及最后廉价咖啡位置以前的eligible。遇廉价点，令epoch加1；某色第一次在新epoch出现时把其eligible刷新为当前total，相当于取得该颜色在廉价点前的前缀数。每到一家酒店累加eligible，再增加total；若本酒店廉价，还要把自身纳入供后续酒店使用的eligible。

正确性说明

固定右端酒店时，合法左端恰为同色且不晚于最后廉价咖啡位置的所有旧酒店。延迟刷新前，这个颜色在新epoch尚未再出现，所以total仍等于该位置以前数量；同epoch内eligible保持不变，避免把无廉价点的新酒店误算。廉价酒店自身作为后续左端必须在本步末加入，因而逐右端累加无重不漏。

复杂度

初始化O(k)，扫描O(n)，总O(n+k)时间，O(k)辅助空间，不保存200万酒店全部输入。

易错点

咖啡店允许位于两端。先计旧酒店再加当前酒店，防止一人住同一家。当前廉价酒店要更新自身颜色的eligible，漏此步会少算后续配对。总方案数用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, p;
    cin >> n >> k >> p;
    vector<int> total(k), eligible(k), stamp(k, -1);
    int epoch = 0;
    long long ans = 0;
    for (int i = 0, c, v; i < n; i++) {
        cin >> c >> v;
        if (v <= p)
            epoch++;
        if (stamp[c] != epoch) {
            eligible[c] = total[c];
            stamp[c] = epoch;
        }
        ans += eligible[c];
        total[c]++;
        if (v <= p)
            eligible[c] = total[c];
    }
    cout << ans << '\n';
}