首页 > 代码库 > hiho一下 第二十一周（线段树 离散化）
hiho一下 第二十一周（线段树 离散化）
知识点1：离散化
对于这些区间来说，其实并不会在乎具体数值是多少，而是在他们的左右端点之间互相进行比较而已。所以你就把这N个区间的左右端点——2N个整数提出来，处理一下呗？你要注意的是，这2N个数是什么其实并不重要，你可以把这2N个数替换成为任何另外2N个数，只要他们之间的相对大小关系不发生改变就可以。”
解决方法：
那么我需要额外做的事情就是在构建线段树之前对区间进行预处理：将区间的左右端点选出来，组成一个集合，然后将这个集合依次对应到正整数集合上，并且利用这个对应将原来的区间的左右端点更换为新的值。这样新构建的区间在这个问题中的答案和原来区间是一样的，但是新区间的范围就是O(N)这个级别的，我就可以用O(N)的时间复杂度和空间复杂度构建出线段树了！”
知识点2： 线段树的节点意义
在线段树的通常用法中，线段树的节点是有2种不同的意义的，一种是离散型的，比如在Hiho一下 第二十周中，一个节点虽然描述的是一个区间[3, 9]，但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。而另一种就是连续型的，比如就在这一周的问题中，一个节点如果描述的是一个区间[3, 9]，它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。
那么有的小朋友可能就要问了，这两种不同的意义有什么区别呢？
在小Hi看来，其实只有这样的几个区别：1.叶子节点：在离散型中，叶子节点是[i, i]，而连续性中是[i, i + 1]；2.分解区间：在离散型中，一段区间是分解成为[l, m], [m + 1, r]，而在连续型中，是分解成为[l, m], [m, r]；3.其他所有类似的判定问题。
1 #include<string.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<map> 6 using namespace std; 7 #define MAXN 200010 8 int tree[MAXN<<1]; 9 int num[MAXN];10 int ans[MAXN];//记录最后以否已经被统计11 map<int,int >mp;12 #define lson l,m,rt<<113 #define rson m,r,rt<<1|114 struct node15 {16 int x,y;17 };18 node a[MAXN];19 int re = 0;20 21 void PushDown(int rt)22 {23 if (tree[rt]) {24 tree[rt<<1] = tree[rt<<1|1] = tree[rt];25 tree[rt] = 0;26 return;27 }28 return;29 }30 31 void update(int L,int R,int c,int l,int r,int rt)32 {33 if (L <= l && R >= r) {34 tree[rt] = c;35 return;36 }37 if (l + 1 == r) return;38 PushDown(rt);39 int m = (l + r) >>1;40 if (L <= m) update(L, R, c, lson);41 if (R > m) update(L, R, c, rson);42 return;43 }44 45 void query(int L, int R, int l, int r, int rt)46 {47 if (tree[rt] != 0 && ans[tree[rt]] == 0) {48 ans[tree[rt]] = 1;49 re++;50 return;51 }52 if (l + 1 == r) return;53 PushDown(rt);54 int m = (l + r) >> 1;55 if (L <= m) 56 query(L,R,lson);57 if (R > m) 58 query(L,R,rson);59 return;60 }61 62 int main()63 {64 int n,l;65 cin >> n >> l;66 int all=0;67 for(int i=1;i<=n;i++)68 {69 cin >> a[i].x >> a[i].y;70 num[all++]=a[i].x;71 num[all++]=a[i].y;72 }73 sort(num,num+all);74 int all2=1;75 for(int i=0;i<all;i++)76 if(mp[num[i]]==0)77 {78 mp[num[i]]=all2++;79 }80 //for(int i=1;i<=n;i++)81 // cout<<mp[a[i].x]<<" "<<mp[a[i].y]<<endl;82 all=all2-1;83 //cout<<all<<endl;84 for(int i = 1;i<= n;i++)85 {86 update(mp[a[i].x],mp[a[i].y],i,1,all,1);87 }88 query(1,all,1,all,1);89 printf("%d\n",re);90 system("pause");91 return 0;92 }
hiho一下 第二十一周（线段树 离散化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。