[NOIP2011-提高] 选择客栈

题目描述

$n$ 家客栈排成一排，第 $i$ 家有色调 $c_i$ （ $0\sim k-1$ ）和咖啡店最低消费 $b_i$ 。统计有多少对 $i<j$ 满足：

色调相同 $c_i=c_j$ ；
区间 $[i,j]$ 内至少有一家咖啡店消费不超过 $p$ 。

输入： $n,k,p$ ，随后 $n$ 行每行 $c_i,b_i$ 。
输出：合法方案总数。
数据范围： $2\le n\le 200\,000$ ， $0\le k\le 10\,000$ 。

样例： $n=5,k=2,p=3$ ，客栈依次为 $(0,5),(1,3),(0,2),(1,4),(1,5)$ ，输出 $3$ 。

思路

固定右端点 $j$ ，设 $L(j)$ 为 $[1,j]$ 中最靠右的低价店位置。区间 $[i,j]$ 合法当且仅当 $i\le L(j)$ 。扫描时维护 total[c]（该色已出现次数）、valid[c]（位置 $\le L$ 的该色次数）和 pending（ $L$ 右侧暂存的色调）。若 $b_j\le p$ 则 ans += total[c] 并清空 pending 补入 valid；否则 ans += valid[c] 并把 $c_j$ 加入 `pending $。一趟 $O(n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/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-10-02 09:16
# update_at: 2026-10-02 09:16

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k, p = next(data), next(data), next(data)

    total = [0] * k      # 每种色调已经出现过的客栈数
    valid = [0] * k      # 每种色调中「位置不超过最近一家低价店」的客栈数
    pending: list[int] = []  # 最近一家低价店之后出现的色调，还没计入 valid
    ans = 0

    for _ in range(n):
        color, price = next(data), next(data)
        if price <= p:
            # 本店就是低价店：任何之前的同色客栈与它配对都合法（区间含右端点）
            ans += total[color]
            # 上次低价店到本店之间的客栈，现在都落在最新低价店左侧（含），补计入
            for col in pending:
                valid[col] += 1
            pending.clear()
            valid[color] += 1  # 本店自身也是低价店，对更靠右的客栈可用
        else:
            # 区间内要有低价店，只有位置在最近低价店左侧（含）的同色客栈才可配对
            ans += valid[color]
            pending.append(color)
        total[color] += 1

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * 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 14:42
 * update_at: 2026-10-06 14:42
 */
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXK = 10005; // 色调数上限

int n, k;
ll p;
int total[MAXK]; // 每种色调已出现的客栈数
int valid[MAXK]; // 每种色调中位置不超过最近低价店的客栈数
int pending[MAXK]; // 暂存最近低价店之后出现的色调，补记时一次性处理
int pending_cnt;   // pending 当前长度

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

    cin >> n >> k >> p;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        int color;
        ll price;
        cin >> color >> price;
        if (price <= p) {
            // 本店是低价店：之前所有同色客栈都与它合法
            ans += total[color];
            // 把 pending 里的客栈全部补入 valid
            for (int j = 0; j < pending_cnt; ++j) {
                valid[pending[j]]++;
            }
            pending_cnt = 0;
            valid[color]++; // 本店自身对更右侧客栈可用
        } else {
            // 只能与最近低价店左侧（含）的同色客栈配对
            ans += valid[color];
            pending[pending_cnt++] = color;
        }
        total[color]++;
    }
    cout << ans << "\n";
    return 0;
}