#P12466. [2025年福建省队集训]篱莘龙

    ID: 11629 传统题 3000ms 888MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-消除被支配候选懒标记线段树树状数组有序集合

[2025年福建省队集训]篱莘龙

题目描述

Yuki 家里养着 nn 只奶龙,第 ii 只奶龙的攻击力为 aia_i,防御力为 bib_i。

对于第 ii 只奶龙和第 jj 只奶龙(i≠ji\ne j),如果 ai>bja_i>b_j,则第 ii 只奶龙会攻击第 jj 只奶龙。

你需要对于每个不大于 nn 的正整数 kk 求出,在第 11 只奶龙到第 kk 只奶龙中,最多可以选择多少只奶龙,使得这些奶龙中不存在某只奶龙会攻击另一只奶龙。

输入格式

从 loong.in 中读入数据。

  • 第一行包含一个正整数 cc,表示测试点编号。样例满足 c=0c=0。
  • 第二行包含一个正整数 nn。
  • 接下来 nn 行,第 ii 行包含两个正整数 ai,bia_i,b_i。保证所有 ai,bia_i,b_i 互不相同。

输出格式

输出到 loong.out 中。

输出 nn 行,第 ii 行包含一个整数,表示 k=ik=i 时的答案。

样例 1 输入

0
3
1 6
3 2
5 4

样例 1 输出

1
2
2

样例 1 解释

  • k=1k=1 时显然只能选择第一只奶龙。
  • k=2k=2 时可以选择前两只奶龙。
  • k=3k=3 时,如果选择全部奶龙,则第三只奶龙会攻击第二只奶龙。所以答案最多为 22。

样例 2

见 loong/loong2.in 与 loong/loong2.ans。

样例 3

见 loong/loong3.in 与 loong/loong3.ans。

样例 4

见 loong/loong4.in 与 loong/loong4.ans。

样例 5

见 loong/loong5.in 与 loong/loong5.ans。

样例 6

见 loong/loong6.in 与 loong/loong6.ans。

样例 7

见 loong/loong7.in 与 loong/loong7.ans。

数据范围

对于所有测试数据,保证:

  • 1≤n≤1061 \le n \le 10^6;
  • 1≤ai,bi≤2n1 \le a_i,b_i \le 2n,所有 ai,bia_i,b_i 互不相同。
测试点编号 n≤n\le 特殊性质
11 2020 无
2∼32\sim 3 400400
44 20002000 B
5∼65\sim 6 无
77 2×1052\times 10^5 C
8∼108\sim 10 无
1111 10610^6 A
1212 B
1313 C
14∼1614\sim 16 5×1055\times 10^5 无
17∼2017\sim 20 10610^6
  • 特殊性质 A:保证 ai>bia_i> b_i。
  • 特殊性质 B:保证 ai<bia_i< b_i。
  • 特殊性质 C:保证只有不超过 100100 只奶龙满足 ai<bia_i<b_i。