如果把实验品看成平面直角坐标系上的点的话，每个实验品所被分到的组的编号就是其右上角所有实验品的组的编号的最大值 \(+ 1\)。
因为显然要把包含它的所有实验品先分完才能考虑它的分组。
那么，我们可以考虑把所有实验品按照 \(D\) 降序排序，并在 \(D\) 相同时按 \(R\) 升序排序。
至于为什么一个降序一个升序，这是因为题目中的关系是严格大于，所以 \(D\) 相同的实验品之间都不会互相有贡献，通过升序来排除。
然后，因为排了序，所以不需要考虑 \(D\) 的影响。
对于 \(R\)，在权值线段树里维护即可。
其实我比赛时写了个树套树但是貌似没有考虑好细节挂掉了。
代码： 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
52
53
54
55
56
57
58
59
60
using namespace std;
const int N = 1e5;
const int A = 1e9;
int n,ans[N + 5];
struct note
{
int d,r,id;
inline bool operator>(const note &o) const
{
return d > o.d || (d == o.d && r < o.r);
}
} a[N + 5];
struct node
{
int max,ls,rs;
} seg[(N << 5) + 10];
int rt;
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
if(tl == tr)
{
seg[p].max = k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
insert(x,k,seg[p].ls,tl,mid);
else
insert(x,k,seg[p].rs,mid + 1,tr);
seg[p].max = max(seg[seg[p].ls].max,seg[seg[p].rs].max);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].max;
int mid = tl + tr >> 1;
int ret = 0;
if(l <= mid)
ret = max(ret,query(l,r,seg[p].ls,tl,mid));
if(r > mid)
ret = max(ret,query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&a[i].d,&a[i].r),a[i].id = i;
sort(a + 1,a + n + 1,greater<note>());
for(register int i = 1;i <= n;++i)
insert(a[i].r,(ans[a[i].id] = query(a[i].r,A,rt,1,A) + 1),rt,1,A);
for(register int i = 1;i <= n;++i)
printf("%d\n",ans[i]);
}