开始没想到用离散化，对线段树也只在标记线段，而无法想到着色的巧妙方法。本题关键在于对已经着色线段内的子线段着色时，需要将此线段的颜色先下沉到孩子结点再着色，另一个要点便是查询时遇到有色线段直接返回递归。这点注意到了，结果在代码里没有体现，出现了好几次莫名的WA。
开始入门的时候很艰难，对代码细节很难把握，并且时间一长，查错也变的很困难了。
well 最后采用从AC代码改回我代码的方法值得在无法解决问题时使用
less well 基本功还需要加强，特别是细节，一定不能忽视。
/**//*
* Doc Name: Mayor's posters
* Prob Id: 2528
* Serial Id: 1
* Author: LTE
* Date: 10/10/25
*/
#include <iostream>
#include <algorithm>
using namespace std;
int i,j,k;
int a[10001],b[10001];
int map[20002];
int f[10000001];
int nc,ns;
bool color[10002];
int cnt;
struct Node
{
int l,r,mid,c;
};
Node tree[10001*10];
int cmp(const void* a, const void *b)
{
return *(int*)a < *(int*)b;
}
void buildTree(const int l, const int r, const int pos)
{
tree[pos].l = l;
tree[pos].r = r;
tree[pos].c = 0;
tree[pos].mid = (l+r)>>1;
if(l==r-1) return;
buildTree(l, tree[pos].mid, pos<<1);
buildTree(tree[pos].mid, r, pos<<1|1);
}
void insert(const int pos, const int l, const int r, const int c)
{
if(l==tree[pos].l && r== tree[pos].r)
{
tree[pos].c = c;
return;
}
if(tree[pos].c > 0)
{
tree[pos<<1].c = tree[pos<<1|1].c = tree[pos].c;
tree[pos].c = 0;
}
if(r<=tree[pos].mid)
{
insert(pos<<1, l, r, c);
}
else if(l>=tree[pos].mid)
{
insert(pos<<1|1, l, r, c);
}
else
{
insert(pos<<1, l, tree[pos].mid, c);
insert(pos<<1|1, tree[pos].mid, r, c);
}
}
void query(int pos)
{
if(tree[pos].c)
{
if(color[tree[pos].c]==false)
{
cnt++;
color[tree[pos].c] = true;
}
return;
}
if(tree[pos].l == tree[pos].r - 1)
return;
query(pos<<1);
query(pos<<1|1);
}
int main()
{
//!! delete while submit!!!
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &nc);
while(nc--)
{
scanf("%d", &ns);
for(i=0; i<ns; ++i)
{
scanf("%d%d", &a[i], &b[i]);
a[i]--;
map[i<<1] = a[i];
map[i<<1|1] = b[i];
}
sort(map, map+(ns<<1));
j=1;
f[map[0]]=j;
for(i=1; i<(ns<<1); i++)
{
if(map[i]!=map[i-1]) f[map[i]]=++j;
}
buildTree(1, j, 1);
for(i=0; i<ns; ++i)
{
insert(1, f[a[i]], f[b[i]], i+1);
}
memset(color, 0, sizeof(color));
cnt = 0;
query(1);
printf("%d\n", cnt);
}
return 0;
}