gzwzm06
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
<
2024年11月
>
日
一
二
三
四
五
六
27
28
29
30
31
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
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年5月 (1)
文章分类
DP(12)
(rss)
Hash应用(4)
(rss)
几何(1)
(rss)
模拟题(2)
(rss)
数据结构(12)
(rss)
数学(2)
(rss)
搜索(2)
(rss)
图论(7)
(rss)
与Tree相关的题(2)
(rss)
字符串处理(8)
(rss)
文章档案
2009年5月 (8)
2009年4月 (5)
2009年3月 (14)
2008年11月 (20)
2008年10月 (5)
搜索
最新评论
1. re: Pku 2774--Long Long Message(后缀树)
求教大牛,那个Lt属性是记录什么的
--dereky
2. re: POJ 2481(树状数组)
@gzwzm06
哦,实在是不好意思,确实是那个地方,现在过了,谢谢了啊。
--Klion
3. re: POJ 2481(树状数组)
你再检查下,cc[j].m_e == cc[j].m_e这个条件肯定是真的,没有意义吧
--gzwzm06
4. re: POJ 2481(树状数组)
@gzwzm06
两个相同一起比较也就是两个区间是一样的,起点和终点是相同的,和您的第80行比较的应该是一样的吧?
--Klion
5. re: POJ 2481(树状数组)
评论内容较长,点击标题查看
--gzwzm06
POJ 2528(离散化 + 线段树)
1
#include
<
cstdio
>
2
#include
<
memory.h
>
3
#include
<
algorithm
>
4
using
namespace
std ;
5
6
const
int
MAXN
=
41001
;
7
const
int
SIZE
=
10001
;
8
9
struct
NODE
10
{
11
int
m_flag ;
12
int
m_start, m_end ;
13
NODE
*
leftc ,
*
rightc ;
14
15
void
BuildTree(
const
int
&
s,
const
int
&
e) ;
16
void
Insert(
const
int
&
s,
const
int
&
e,
const
int
&
k) ;
17
void
FindInTree() ;
18
}
;
19
20
struct
WALL
21
{
22
int
m_pos ;
23
int
m_value ;
24
25
bool
const
operator
<
( WALL
&
b )
const
26
{
27
if
( m_value
<
b.m_value )
28
return
true
;
29
return
false
;
30
}
31
}
wall[SIZE
*
2
] ;
32
33
NODE
*
root ;
34
NODE Stree[MAXN] ;
35
int
g_Pos ;
36
int
ans , arrSize ;
37
int
gFlag[SIZE] ;
38
39
void
NODE::BuildTree(
const
int
&
s,
const
int
&
e)
40
{
41
m_flag
=
0
;
42
m_start
=
s, m_end
=
e ;
43
if
( e
==
s )
44
{
45
leftc
=
rightc
=
NULL ;
46
return
;
47
}
48
49
int
mid
=
( s
+
e )
>>
1
;
50
51
leftc
=
&
Stree[g_Pos
++
] ;
52
rightc
=
&
Stree[g_Pos
++
] ;
53
54
leftc
->
BuildTree(s, mid) ;
55
rightc
->
BuildTree(mid
+
1
, e) ;
56
57
}
58
59
void
NODE::Insert(
const
int
&
s,
const
int
&
e,
const
int
&
k)
60
{
61
if
( m_start
==
m_end )
62
{
63
m_flag
=
k ;
64
return
;
65
}
66
if
( m_start
==
s
&&
m_end
==
e )
67
{
68
m_flag
=
k ;
69
return
;
70
}
71
if
( m_flag
>
0
)
{
72
rightc
->
m_flag
=
m_flag ;
73
leftc
->
m_flag
=
m_flag ;
74
m_flag
=
-
1
;
75
}
76
else
if
( m_flag
==
0
)
77
m_flag
=
k ;
78
79
int
mid
=
( m_start
+
m_end )
>>
1
;
80
81
if
( mid
>=
e )
82
{
83
leftc
->
Insert( s, e, k ) ;
84
}
85
else
if
( mid
<
s )
//
就这里,写多了一个等号,导致WA十几次
86
{
87
rightc
->
Insert( s, e, k ) ;
88
}
89
else
{
90
leftc
->
Insert( s, mid, k ) ;
91
rightc
->
Insert( mid
+
1
, e, k ) ;
92
}
93
}
94
95
void
NODE::FindInTree()
96
{
97
if
( m_flag
>=
0
)
98
{
99
if
( gFlag[m_flag]
==
0
)
100
{
101
gFlag[m_flag]
=
1
;
102
ans
++
;
103
}
104
return
;
//
不需要访问到叶节点
105
}
106
107
if
( m_flag
==
-
1
)
108
{
109
leftc
->
FindInTree() ;
110
rightc
->
FindInTree() ;
111
}
112
113
}
114
115
void
Init()
116
{
117
ans
=
0
;
118
g_Pos
=
1
;
119
root
=
&
Stree[
0
] ;
120
121
root
->
leftc
=
root
->
rightc
=
NULL ;
122
memset(gFlag,
0
,
sizeof
(gFlag)) ;
123
}
124
int
main()
125
{
126
//
freopen("in.txt", "r", stdin) ;
127
128
int
T , n , i , size , x , y ;
129
int
pos[SIZE][
2
] ;
130
scanf(
"
%d
"
,
&
T) ;
131
132
while
( T
--
)
133
{
134
Init() ;
135
size
=
0
;
136
137
scanf(
"
%d
"
,
&
n) ;
138
139
for
( i
=
1
; i
<=
n ;
++
i )
140
{
141
scanf(
"
%d %d
"
,
&
pos[i][
0
],
&
pos[i][
1
]) ;
142
wall[size].m_pos
=
i ;
143
wall[size
++
].m_value
=
pos[i][
0
] ;
144
wall[size].m_pos
=
-
i ;
145
wall[size
++
].m_value
=
pos[i][
1
] ;
146
}
147
//
离散化
148
sort(wall, wall
+
size) ;
149
150
x
=
1
;
151
if
( wall[
0
].m_pos
<
0
)
152
pos[
-
wall[
0
].m_pos][
1
]
=
1
;
153
else
154
pos[wall[
0
].m_pos][
0
]
=
1
;
155
156
for
( i
=
1
; i
<
size ;
++
i )
157
{
158
if
( wall[i].m_value
!=
wall[i
-
1
].m_value )
159
{
160
x
++
;
161
}
162
if
( wall[i].m_pos
>
0
)
163
pos[wall[i].m_pos][
0
]
=
x ;
164
else
165
pos[
-
wall[i].m_pos][
1
]
=
x ;
166
167
}
168
169
arrSize
=
x ;
170
//
线段树
171
root
->
BuildTree(
1
, arrSize ) ;
172
173
for
( i
=
1
; i
<=
n ;
++
i )
174
{
175
x
=
pos[i][
0
] ;
176
y
=
pos[i][
1
] ;
177
root
->
Insert( x, y, i ) ;
178
}
179
180
root
->
FindInTree() ;
181
182
printf(
"
%d\n
"
, ans) ;
183
}
184
return
0
;
185
}
186
187
188
189
posted on 2008-11-16 20:58
巫
阅读(435)
评论(0)
编辑
收藏
引用
所属分类:
数据结构
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
7th GDCPC Problem H(DFS序 + 线段树)
POJ 3368 (RMQ)
POJ 3368 Frequent values (线段树)
POJ 2060--Taxi Cab Scheme(最小路径覆盖)
Atomic Nucleus Investigation (线段树 n = 100000)
POJ 2481(树状数组)
POJ 2481 Cows(线段树)
POJ 3667 Hotel(模拟)
Pku 2828(线段树)
Pku 2777(线段树)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 巫