開始沒想到用離散化，對線段樹也只在標記線段，而無法想到著色的巧妙方法。本題關(guān)鍵在于對已經(jīng)著色線段內(nèi)的子線段著色時，需要將此線段的顏色先下沉到孩子結(jié)點再著色，另一個要點便是查詢時遇到有色線段直接返回遞歸。這點注意到了，結(jié)果在代碼里沒有體現(xiàn)，出現(xiàn)了好幾次莫名的WA。
開始入門的時候很艱難，對代碼細節(jié)很難把握，并且時間一長，查錯也變的很困難了。
well 最后采用從AC代碼改回我代碼的方法值得在無法解決問題時使用
less well 基本功還需要加強，特別是細節(jié)，一定不能忽視。
/**//*
* 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;
}