//离散化+线段树
(以下转)感谢它帮助我理解离散化
假如不离散化，那线段树的上界是10^7，假如建一个那么大的线段树的话。。。必然MLE。于是要考虑离散化。
离散化的目的就是要将线段的长度适当的缩小，但不破坏题意。
比如：
------ （1，6）
------------ （1，12 ）
像这样这样的两条线段，可以把它们看作：
-- （1，2）
--- （ 1，3 ）
这样，缩短了线段的长度，但是他们的覆盖关系并没有改变。
关键我们要重新给压缩后的线段标记起点和终点。
按照通用的离散化方法。。。。
首先依次读入线段端点坐标，存于post[MAXN][2]中，post[i][0]存第一条线段的起点，post[i][1]存第一条线段的终点，然后用一个结构题数组line[MAXN]记录信息，hash[i].v记录端点坐标，hash[i].line记录这个点属于哪条线段（用正负数表示，负数表示起点，正数表示终点）。假如有N条线段，就有2*N个端点。然后将hash数组排序，按照端点的坐标，从小到大排。接着要把线段赋予新的端点坐标了。从左到右按照递增的次序，依次更新端点，假如2*N个点中，共有M个不同坐标的点，那么线段树的范围就是[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; //端点值
15 int line; //属于哪条线段,-起,+终
16};
17
18seg Segtree[MAX_UNSIGEN+2]; //数
19bool colortable[MAXN+1];
20int post[MAXN][2]; //记录输入的poster位置,post[i][0]起点,post[i][0]终点
21structx hash[2*MAXN+1]; //所有端点,对其排序,相当于一个映射表
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 阅读(271)
评论(0) 编辑 收藏 引用 所属分类:
POJ