poj 2528(线段树)

poj 2528
线段树离散化区间后区间染色,注意离散化问题

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 10000 + 5;
const int LEFT = 0, RIGHT = 1;
struct poi
{
int a, from, f;
//a为坐标,from为该点来源,f为是否左右结点
bool operator <(const poi &b) const
{
return a<b.a;
}
}p[MAXN*2];
struct ls
{
int ch[2];//离散化后的线段
}seg[MAXN];
int n;
#define lc o*2
#define rc o*2+1
#define M (l+r)/2
struct st
{
int col[MAXN*4*4];//为-1则无颜色
void pushdown(int o)
{
if (col[o]!=-1)
{
col[lc] = col[rc] = col[o];
col[o] = -1;
}
}
void build(int o, int l ,int r)
{
col[o] = -1;
if (l==r) return ;
build(lc, l, M);
build(rc, M+1, r);
}
void update(int o, int l, int r, int x, int y, int c)
{
if (x<=l&&r<=y)
{
col[o] = c;
return ;
}
pushdown(o);
if (x<=M) update(lc, l, M, x, y, c);
if (M<y) update(rc, M+1, r, x, y, c);
}
bool used[MAXN*2*4];
int query(int o, int l, int r, int x, int y)
{
if (col[o]!=-1)
{
if (!used[col[o]])
{
used[col[o]] = true;
return 1;
}else {
return 0;
}
}
int ans = 0;
if (x<=M) ans += query(lc, l, M, x, y);
if (M<y) ans += query(rc, M+1, r, x, y);
return ans;
}
}tree;
int main()
{
int kase;
scanf("%d", &kase);
while (kase--)
{
scanf("%d", &n);
for (int i=0;i<n;i++)
{
int x,y;
scanf("%d%d", &x, &y);
p[i*2].a = x, p[i*2].from = i, p[i*2].f = LEFT;
p[i*2+1].a = y, p[i*2+1].from = i, p[i*2+1].f = RIGHT;
}
sort(p, p+n*2);
//处理第一个
int last = p[0].a;
int now = 1;
seg[p[0].from].ch[p[0].f] = now;
for (int i=1;i<2*n;i++)
{
if (p[i].a!=p[i-1].a)now++;
if (p[i].a-last>1) now++; //离散化要在相距大于1的两个数之间加一个数!
seg[p[i].from].ch[p[i].f] = now;
last = p[i].a;
}
tree.build(1,1,now);
for (int i=0;i<n;i++) tree.update(1,1,now,seg[i].ch[0], seg[i].ch[1], i);
ms(tree.used, false);
printf("%d\n", tree.query(1,1,now,1,now));
}
return 0;
}

------ 本文结束 ------