24 小时滑动窗口统计不同国籍数：船整进整出队列，国籍计数 +1/-1，减到 0 删键，答案 O(1)。
OJ: roj
题目 ID: 3636
难度:普及-
标签:滑动窗口队列计数python
创建: 2026-10-02 12:07
更新: 2026-10-07 13:50
题目描述
小 K 在海港按时间记录了
输入：第一行一个正整数
数据范围：
样例 1：输入 3、1 4 4 1 2 2、2 2 2 3、10 1 3，输出依次为 3、4、4。
思路
cnt[国籍] 维护窗口内人数，减到 0 时不同国籍数 distinct 减一，每轮直接输出 distinct；每个乘客只进、出各一次，总复杂度
参考代码
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-10-02 12:10
# update_at: 2026-10-02 12:14
import sys
from collections import deque
from collections.abc import Iterator
WINDOW = 86400 # 统计窗口：船到达时刻往前 24 小时 = 86400 秒
def read_ships(lines: Iterator[bytes]) -> Iterator[tuple[int, list[int]]]:
"""从标准输入的行流里依次产出 (到达时间, 国籍列表)，逐行读入、不整份驻留内存。
每行前两个数是到达时间 t 和乘客数 k，其后恰好 k 个国籍。
"""
n = int(next(lines))
for _ in range(n):
t, k, *nats = map(int, next(lines).split()) # k 只用于占位，国籍个数由行本身给出
yield t, nats
def window_answers(ships: Iterator[tuple[int, list[int]]]) -> Iterator[int]:
"""依次产出每艘船到达后，窗口 (t-86400, t] 内的不同国籍数。
船按到达时间递增，退出窗口的船只会出现在队首，整船出窗即可；
计数归零的国籍立即删键，len(counter) 才恒等于窗口内的国籍数。
"""
window: deque[tuple[int, list[int]]] = deque() # 窗口内的船 (到达时间, 国籍列表)
counter: dict[int, int] = {} # 窗口内每个国籍的人数
for t, nats in ships:
window.append((t, nats))
for x in nats:
counter[x] = counter.get(x, 0) + 1
expire_before = t - WINDOW # 早于该时刻到达的船已滑出 24 小时窗口
while window[0][0] <= expire_before:
_, old = window.popleft()
for x in old:
if counter[x] == 1:
del counter[x] # 该国籍在窗口内只剩这一个人，随船一起消失
else:
counter[x] -= 1
yield len(counter)
def solve() -> None:
ships = read_ships(sys.stdin.buffer)
write = sys.stdout.buffer.write
for answer in window_answers(ships):
write(f"{answer}\n".encode()) # 逐行输出，不攒整份答案字符串
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 15:52
* update_at: 2026-10-06 15:52
*/
#include <cstdio>
typedef long long ll;
const int MAXN = 100005; // 船的数量上限
const int MAXP = 300005; // 乘客总数上限（sum k <= 3*10^5）
const int MAXC = 100005; // 国籍的值域上限
ll tim[MAXN]; // tim[i]：第 i 艘船的到达时间（秒）
int pcnt[MAXN]; // pcnt[i]：第 i 艘船的乘客数
int pst[MAXN]; // pst[i]：第 i 艘船的乘客在 nat[] 中的起始下标
int nat[MAXP]; // nat[]：按船的顺序展开存放的所有乘客国籍
int cnt[MAXC]; // cnt[c]：当前 24 小时窗口内国籍为 c 的乘客人数
int n; // 船的数量
int tot = 0; // nat[] 已存放的乘客总数
int left_id = 1; // 窗口最左端还没过期的船的编号
int distinct = 0; // 当前窗口内不同国籍的数量
// 把第 i 艘船整船放进窗口：船上每个乘客的国籍计数 +1
// 船 i 的乘客存放在 nat[pst[i]+1 .. pst[i]+pcnt[i]]（nat 从 1 开始存放）
void add_ship(int i) {
for (int p = pst[i] + 1; p <= pst[i] + pcnt[i]; p++) {
int c = nat[p];
if (cnt[c] == 0) distinct++; // 这个国籍第一次进入窗口
cnt[c]++;
}
}
// 把第 i 艘船整船移出窗口：船上每个乘客的国籍计数 -1
void remove_ship(int i) {
for (int p = pst[i] + 1; p <= pst[i] + pcnt[i]; p++) {
int c = nat[p];
cnt[c]--;
if (cnt[c] == 0) distinct--; // 这个国籍完全离开了窗口
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %d", &tim[i], &pcnt[i]);
pst[i] = tot; // 船 i 的乘客从 nat[tot+1] 开始存放
for (int j = 1; j <= pcnt[i]; j++) {
tot++; // 先确定本乘客的下标，再读入
scanf("%d", &nat[tot]);
}
}
for (int i = 1; i <= n; i++) {
add_ship(i); // 右端：第 i 艘船进窗
// 左端：t_i 递增保证过期船都在队首，整船弹出；
// 窗口是开左闭右区间 (t_i-86400, t_i]，取等即出
while (left_id <= i && tim[left_id] <= tim[i] - 86400) {
remove_ship(left_id);
left_id++;
}
printf("%d\n", distinct);
}
return 0;
}