从左到右扫描，用 covered[c] 维护位置已进入最靠右便宜咖啡店左侧的同色客栈数，答案每次累加 covered[c_j]，O(n) 时间、O(k) 空间。
OJ: roj
题目 ID: 1546
难度:普及
标签:计数思维python
创建: 2026-09-30 17:20
更新: 2026-10-07 13:50
题目描述
丽江河边有
输入第一行 5 2 3 / 0 5 / 1 3 / 0 2 / 1 4 / 1 5，样例输出 3；
思路
对固定右端点 covered[c] 维护位置已进入 covered[c_j]。时间
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:25
# update_at: 2026-10-04 15:07
import sys
from collections.abc import Iterator
def count_pairs(inns: Iterator[tuple[int, int]], k: int, p: int) -> int:
"""统计合法住宿方案数：两店同色，且它们之间（含端点）存在消费 <= p 的咖啡店。
消费 <= p 的咖啡店会把它之后（含自己）的所有客栈变成"合法左端点"，所以
合法方案数 = 出现过的同色客栈数 - 还没被便宜咖啡店覆盖到的同色客栈数；
后者记在欠账 pend 里，碰到便宜咖啡店就一笔清零。
"""
total = [0] * k # 各色调出现过的客栈数：历史左端点候选总数
pend: dict[int, int] = {} # 欠账：尚未被便宜咖啡店覆盖的客栈，按色调计数
ans = 0
for color, price in inns:
cheap = price <= p
if cheap:
pend.clear() # 本店咖啡店够便宜：欠账全部转为合法
uncovered = pend.get(color, 0) # 刚清零时恒为 0，两种分支可共用
ans += total[color] - uncovered # 同色前缀里合法的左端点数量
total[color] += 1
if not cheap:
pend[color] = uncovered + 1 # 本店自己还欠着，记一笔
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, k, p = next(data), next(data), next(data) # 题面的 n 家客栈、k 种色调、阈值 p
inns = ((next(data), next(data)) for _ in range(n)) # 逐家产出 (色调, 最低消费)
print(count_pairs(inns, k, p))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 00:41
* update_at: 2026-10-06 00:41
*/
#include <cstdio>
const int MAXN = 2000005;
const int MAXK = 10005;
int col[MAXN]; // col[i] 表示第 i 家客栈的色调
int covered[MAXK]; // covered[c]：阈值 g 左侧（位置 <= g）色调为 c 的客栈数，即可作合法左端点的数量
int main() {
int n, k, p;
scanf("%d %d %d", &n, &k, &p);
int g = 0; // g：目前为止最靠右的便宜咖啡店位置（消费 <= p），没有则为 0
int last = 0; // last：已经计入 covered 的最右位置，随 g 单调推进
long long ans = 0;
for (int j = 1; j <= n; j++) {
int b;
scanf("%d %d", &col[j], &b);
if (b <= p) g = j; // 出现便宜咖啡店，阈值推进到当前位置
int upto = (g < j) ? g : j - 1; // 只能把位置在 j 之前的客栈计入 covered
while (last < upto) {
last++;
covered[col[last]]++;
}
// 固定右端点 j：合法的左端点恰为位置 <= g 的同色客栈
ans += covered[col[j]];
}
printf("%lld\n", ans);
return 0;
}