大连公司企业网站建设,永济网站建设,一级造价工程师报名,西安哪里找做网站公司1 /*2 poj 2528 Mayors posters 3 线段树 离散化4 5 离散化的理解#xff1a;6 给你一系列的正整数#xff0c; 例如 1#xff0c; 4 #xff0c; 100#xff0c; 1000000000#xff0c; 如果利用线段树求解的话#xff0c;很明显7 会导致内存的耗尽。所以我们做一… 1 /*2 poj 2528 Mayors posters 3 线段树 离散化4 5 离散化的理解6 给你一系列的正整数 例如 1 4 100 1000000000 如果利用线段树求解的话很明显7 会导致内存的耗尽。所以我们做一个映射关系将范围很大的数据映射到范围很小的数据上8 1----1 4-----2 100-----3 1000000000-----49 这样就会减少内存一些不必要的消耗
10 建立好映射关系了接着就是利用线段树求解
11 */
12 #includeiostream
13 #includecstdio
14 #includequeue
15 #includecstring
16 #includealgorithm
17 #define N 10000010
18 #define M 10005
19 using namespace std;
20 class EDGE{
21 public:
22 int ld, rd;
23 };
24 int tree[M*16];//一共有M*2个端点,一个线段映射到四个点左右端点 左端点-1 右端点1 数组的大小是线段树最底层数据个数的4倍
25 EDGE edge[M];
26 int p[M*4];
27 int hash[N];
28 int n;
29
30 int insert(int p, int lr, int rr, int ld, int rd){
31
32 if(tree[p] lrld rdrr)//如果当前的区间[ld, rd]被包含在[lr, rr]中而且[lr, rr]的区间已经被覆盖
33 return 1;
34 else if(lrld rrrd){
35 tree[p]1;
36 return 0;
37 }
38 else{
39 int mid(lrrr)1;
40 int f1, f2, f3, f4;
41 if(midrd)
42 f1insert(p1, lr, mid, ld, rd);
43 else if(midld)
44 f2insert(p1|1, mid1, rr, ld, rd);
45 else{
46 f3insert(p1, lr, mid, ld, mid);
47 f4insert(p1|1, mid1, rr, mid1, rd);
48 }
49 tree[p]tree[p1] tree[p1|1];//两个子树都被覆盖的时候父类才会被覆盖
50 if(midrd)
51 return f1;
52 else if(midld)
53 return f2;
54 else return f3 f4;
55 }
56 }
57 /*
58 3
59 1 10
60 1 3
61 6 10
62 如果将一个线段离散化成两个点输出地结果是2
63 如果是四个节点输出的结果就是3
64 而正确的结果就是3
65 */
66
67 int main(){
68 int t, i, nm;
69 scanf(%d, t);
70 while(t--){
71 int maxR0;
72 scanf(%d, n);
73 for(i0; in; i){
74 scanf(%d%d, edge[i].ld, edge[i].rd);
75 p[maxR]edge[i].ld-1;
76 p[maxR]edge[i].ld;
77 p[maxR]edge[i].rd;
78 p[maxR]edge[i].rd1;
79 }
80 sort(p, pmaxR);
81 maxRunique(p, pmaxR)-p;//元素去重
82 for(i0, nm0; imaxR; i){
83 hash[p[i]]nm;
84 }
85 memset(tree, 0, sizeof(tree));//初始值是所有的点都没有被覆盖
86 int ans0;
87 for(in-1; i0; --i){//由外向里看真是个不错的主意
88 if(!insert(1, 1, nm, hash[edge[i].ld], hash[edge[i].rd]))
89 ans;
90 }
91 printf(%d\n, ans);
92 }
93 return 0;
94 } 转载于:https://www.cnblogs.com/hujunzheng/p/3819362.html
