gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年9月

>

日

一

二

三

四

五

六

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

8

9

10

11

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

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 2481 Cows(線段樹)

1

#include <cstdio>
2

#include <algorithm>
3

using namespace std;
4

5

const int SIZE = 100001;
6

7

struct RANGE
8

{
9

int m_S, m_E;
10

int m_p;
11

12

//按區間右端從大到小排序，再按左端從小到大排
13

//將左端依序插入線段樹，即將區間將大先放入，就能得出包含關系
14

bool operator < (const RANGE& other)
15

{
16

if ( m_E != other.m_E )
17

return (m_E > other.m_E);
18

19

return (m_S < other.m_S);
20

}
21

}cow[SIZE];
22

23

//線段樹
24

struct STREE
25

{
26

int m_leftPos, m_rightPos;
27

int m_left, m_right;
28

int m_ItNum; //記錄區間的左端個數
29

}tree[SIZE * 2];
30

31

int N, result[SIZE];
32

33

void BuildSTree(int& index, const int& l, const int& r)
34

{
35

int id = index;
36

tree[id].m_left = l, tree[id].m_right = r;
37

tree[id].m_ItNum = 0;
38

if ( l == r )
39

{
40

tree[id].m_leftPos = tree[id].m_rightPos = -1;
41

return ;
42

}
43

44

int mid = (l + r) >> 1;
45

46

tree[id].m_leftPos = ++index;
47

BuildSTree( index, l, mid );
48

tree[id].m_rightPos = ++index;
49

BuildSTree( index, mid + 1, r );
50

}
51

52

int Insert(const int& id, const int& s)
53

{
54

int num = 0;
55

if ( tree[id].m_left == s && tree[id].m_right == s )
56

{
57

tree[id].m_ItNum++;
58

return (tree[id].m_ItNum - 1);
59

}
60

61

int mid = (tree[id].m_left + tree[id].m_right) >> 1;
62

63

if ( s <= mid ) {
64

tree[id].m_ItNum++;
65

num += Insert(tree[id].m_leftPos, s);
66

}
67

else {
68

num = tree[id].m_ItNum;
69

num += Insert(tree[id].m_rightPos, s);
70

}
71

72

return num;
73

}
74

75

int main()
76

{
77

freopen("1.txt", "r", stdin);
78

int i, t, maxN;
79

80

while ( true )
81

{
82

scanf("%d", &N);
83

if ( N == 0 )
84

break;
85

86

maxN = 0;
87

for ( i = 0; i < N; ++i )
88

{
89

scanf("%d %d", &cow[i].m_S, &cow[i].m_E);
90

cow[i].m_p = i;
91

if ( cow[i].m_E > maxN )
92

maxN = cow[i].m_E;
93

}
94

t = 0;
95

BuildSTree(t, 0, maxN);
96

sort(cow, cow + N);
97

98

result[cow[0].m_p] = Insert(0, cow[0].m_S);
99

for ( i = 1; i < N; ++i )
100

{
101

result[cow[i].m_p] = Insert(0, cow[i].m_S);
102

//處理區間相等的情況，插入操作還是照做，結果就為等價
103

if ( cow[i].m_E == cow[i - 1].m_E && cow[i].m_S == cow[i - 1].m_S )
104

result[cow[i].m_p] = result[cow[i - 1].m_p];
105

}
106

107

for ( i = 0; i < N - 1; ++i )
108

{
109

printf("%d ", result[i]);
110

}
111

printf("%d\n", result[i]);
112

}
113

return 0;
114

}

posted on 2009-04-11 16:15 巫閱讀(247) 評論(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 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品