//離散化+線段樹(shù)
(以下轉(zhuǎn))感謝它幫助我理解離散化
假如不離散化，那線段樹(shù)的上界是10^7，假如建一個(gè)那么大的線段樹(shù)的話。。。必然MLE。于是要考慮離散化。
離散化的目的就是要將線段的長(zhǎng)度適當(dāng)?shù)目s小，但不破壞題意。
比如：
------ （1，6）
------------ （1，12 ）
像這樣這樣的兩條線段，可以把它們看作：
-- （1，2）
--- （ 1，3 ）
這樣，縮短了線段的長(zhǎng)度，但是他們的覆蓋關(guān)系并沒(méi)有改變。
關(guān)鍵我們要重新給壓縮后的線段標(biāo)記起點(diǎn)和終點(diǎn)。
按照通用的離散化方法。。。。
首先依次讀入線段端點(diǎn)坐標(biāo)，存于post[MAXN][2]中，post[i][0]存第一條線段的起點(diǎn)，post[i][1]存第一條線段的終點(diǎn)，然后用一個(gè)結(jié)構(gòu)題數(shù)組line[MAXN]記錄信息，hash[i].v記錄端點(diǎn)坐標(biāo)，hash[i].line記錄這個(gè)點(diǎn)屬于哪條線段（用正負(fù)數(shù)表示，負(fù)數(shù)表示起點(diǎn)，正數(shù)表示終點(diǎn)）。假如有N條線段，就有2*N個(gè)端點(diǎn)。然后將hash數(shù)組排序，按照端點(diǎn)的坐標(biāo)，從小到大排。接著要把線段賦予新的端點(diǎn)坐標(biāo)了。從左到右按照遞增的次序，依次更新端點(diǎn)，假如2*N個(gè)點(diǎn)中，共有M個(gè)不同坐標(biāo)的點(diǎn)，那么線段樹(shù)的范圍就是[1,M]。
1
#include<iostream>
2#include<stdlib.h>
3#define MAXN 10000
4#define MAX_UNSIGEN 65536
5#define mixcolor -1
6using namespace std;
7struct seg
8
{
9
int left,right;
10 int color;
11
};
12struct structx
13{
14 int v; //端點(diǎn)值
15 int line; //屬于哪條線段,-起,+終
16};
17
18seg Segtree[MAX_UNSIGEN+2]; //數(shù)
19bool colortable[MAXN+1];
20int post[MAXN][2]; //記錄輸入的poster位置,post[i][0]起點(diǎn),post[i][0]終點(diǎn)
21structx hash[2*MAXN+1]; //所有端點(diǎn),對(duì)其排序,相當(dāng)于一個(gè)映射表
22
23void buildsegtree(int v,int l,int r)
24{
25
26 Segtree[v].left=l;
27 Segtree[v].right=r;
28 Segtree[v].color=0;
29 if(l==r) return ;
30
31 int mid=(l+r)>>1; // div 2
32 buildsegtree(v*2,l,mid);
33 buildsegtree(v*2+1,mid+1,r);
34}
35
36void insertseg(int v,int l,int r,int c)
37{
38 if(Segtree[v].left==l && Segtree[v].right==r)
39
{
40 Segtree[v].color=c;
41 return ;
42
}
43 //only one color
44 if(Segtree[v].color != mixcolor )
45 {
46 Segtree[2*v].color=Segtree[v].color;
47 Segtree[2*v+1].color=Segtree[v].color;
48 Segtree[v].color=mixcolor;
49 }
50
51 int mid=(Segtree[v].left + Segtree[v].right) >> 1 ;
52
53 if(r<=mid) insertseg(2*v,l,r,c);
54 else
55 if(mid<l) insertseg(2*v+1,l,r,c);
56 else
57 {
58 insertseg(2*v,l,mid,c);
59 insertseg(2*v+1,mid+1,r,c);
60 }
61}
62
63void count(int v ,int l,int r)
64{
65 if(Segtree[v].color !=mixcolor )
66 {
67 colortable[Segtree[v].color]=true;
68 return ;
69 }
70 int mid=(Segtree[v].left + Segtree[v].right) >> 1;
71 if(r<=mid) count(2*v,l,r);
72 else if(mid<l) count(2*v+1,l,r);
73 else
74 {
75 count(2*v,l,mid);
76 count(2*v+1,mid+1,r);
77 }
78}
79
80int cmp(const void *a,const void *b)
81{
82 return ((structx*)a)->v - ((structx*)b)->v;
83}
84
85int main()
86{
87 int c,n,i,j,cnt,index;
88 scanf("%d",&c);
89 while(c--)
90 {
91 scanf("%d",&n);
92
93 for(i=0,j=0,index=1;i<n;i++)
94 {
95 scanf("%d%d",&post[i][0],&post[i][1]);
96 hash[j].v=post[i][0];hash[j++].line=-index;
97 hash[j].v=post[i][1];hash[j++].line=index++;
98 }
99 //j==2*n
100 //離散化
101 qsort(hash,j,sizeof(hash[0]),cmp);
102 post[-hash[0].line-1][0]=1;
103 for(i=1,index=1;i<j;i++)
104 {
105 if(hash[i].v!=hash[i-1].v) index++;
106
107 if(hash[i].line<0)
108 post[-hash[i].line-1][0]=index;
109 else post[hash[i].line-1][1]=index;
110
111 }
112
113 buildsegtree(1,1,index);
114 for(i=0;i<n;i++)
115 insertseg(1,post[i][0],post[i][1],i+1);
116
117 count(1,1,index);
118 cnt=0;
119 for(i=1;i<=MAXN;i++)
120 if(colortable[i]==true)
121 {
122 cnt++;
123 colortable[i]=false;
124 }
125
126 printf("%d\n",cnt);
127
128 }
129 return 0;
130}
131
posted on 2009-04-17 19:16
wyiu 閱讀(279)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ