首页 > 代码库 > hihocoder 1079 离散化
hihocoder 1079 离散化
题目链接：http://hihocoder.com/problemset/problem/1079 离散化 + 线段树。
这道题卡了我一个多星期，因为我线段树入手不久，基础不牢固，刚开始编出来的时候程序就是崩，这个地方困扰了好几天，后来找到原因后做了改动。改动后程序是不崩了，样例都过不了，后来开始找错误，改思路，昨晚上在实验弄了两个多小时，还是没能弄好。今天数据结构课上想了一节课，把具体的细节给弄清楚了，中午回宿舍开始调试，调试完样例过了，又测了几组数据，觉得没事，交上去，又WA。后来想了一组数据，果然是卡了这组数据，后来上完体育课继续调试，终于找了又找，把几个细节处理好又交了一次，TLE。那会儿想死的心都有了，后来看了hiho上面的十佳代码，发现别人的数组都开的挺大的，于是把maxn扩大一倍，AC。
没啥可说的，好好学习，不当水比。
好了，牢骚发完了，现在开始说下这题的思路，可能会有些混乱。
具体算法：
* 对一个线段(海报的始末位置)进行线段树区间更新，如果找到对应区间则将该区间的更新标记记录一下，对应的线段树区间也对应更新；
* 询问的时候就是遍历整个线段树，如果遇到某区间有标记或者是叶子区间，就将该区间的海报信息记录下来；最后统计一下一共有多少个不同的海报就可以了；
* 注意在更新的时候PushDown()的作用，因为更新到某个区间的时候就意味着这个区间上面就又要贴海报了，而如果没有将这个区间完全覆盖的话那就只需要用到该区间的一个子区间，如果该区间原来是被覆盖过的，就意味着两张海报就要共用这个区间，这时候只能在用在子区间上面了，所以这时候这个区间就要分解开了，所以就是PushDown()操作：标记下放并且原标记取消。
几个注意点：
1.离散化
个人常用的离散化方法：先预存一下数据，然后用数组tmp[]存一下数据，对tmp[]数组排序，然后二分查找原数据在tmp[]数组中的下标，并且把下标作为离散化的数据。有一点比较方便的是，不需要去重。
2.线段树的节点意义
线段树的节点其实是有区别的，比如说离散的区间，就比如说列兵问题，还有就是连续的区间，就是贴海报问题。
两者的最大区别就是在节点上面，离散区间的话如果某区间为[l , r]，那么它的左右儿子区间就是[l , m]，[m + 1 , r]，叶子节点就是一个一个孤立的点; 连续区间就不一样了，因为对连续区间来说点是毫无意义的 ， 所以它的左右儿子区间就是[l , m]，[m , r]，叶子节点就是 [a , a + 1] 。所以对于这两者一定要区别对待，当初就是因为这点没处理好，程序经常崩溃。
hiho原文:
在线段树的通常用法中，线段树的节点是有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.其他所有类似的判定问题。
#include <iostream>#include <iomanip>#include <stdio.h>#include <string.h>#include <algorithm>#include <functional>#include <vector>#include <cmath>#include <string>#include <stack> #include <queue>using namespace std;#define lson l , m , rt << 1 //跟大牛学来的线段树风格#define rson m , r , rt << 1 | 1const int maxn = 200000 + 5; //因为数组开小了，所以 WA + TLE 了很多次int n , l;int tree[maxn << 2] , col[maxn << 2]; //线段树的数组和标记数组int L[maxn][2] , tmp[maxn] , p[maxn]; //离散化用的 void build() { memset(tree , 0 , sizeof(tree)); memset(col , 0 , sizeof(col)); memset(p , 0 , sizeof(p)); }void PushDown(int rt){ if(col[rt]) { tree[rt << 1] = tree[rt << 1 | 1] = tree[rt]; col[rt << 1] = col[rt << 1 | 1] = col[rt]; //因为少了这一句在样例上卡了2个多小时 col[rt] = 0; }}void update(int L , int R , int c , int l , int r , int rt){ if(L <= l && R >= r) { col[rt] = 1; tree[rt] = c; return; } if(l + 1 == r) //因为没有这一句程序还没运行就崩溃，这个延迟了将近一个星期 return; PushDown(rt); int m = (l + r) >> 1; if(m > L) update(L , R , c , lson); if(m <= R) update(L , R , c , rson);}void query(int L , int R , int l , int r , int rt){ if(col[rt] || l + 1 == r) { //查询的边界位置 int i = tree[rt]; p[i]++; return; } int m = (l + r) >> 1; query(L , R , lson); query(L , R , rson);}int binary_Search(int a[] , int l , int r , int x){ //手写二分增加熟练度 int m = (l + r) >> 1; while(l <= r) { if(a[m] == x) return m; if(a[m] < x) l = m + 1; if(a[m] > x) r = m; m = (l + r) >> 1; } return -1;}int main() { int i , j , k; scanf("%d %d", &n , &l); for(i = 1 , k = 0 ; i <= n ; i++) { scanf("%d %d" , &L[i][0] , &L[i][1]); tmp[++k] = L[i][0]; tmp[++k] = L[i][1]; } sort(tmp + 1 , tmp + k + 1); for(i = 1 ; i <= n ; i++) { for(j = 0 ; j <= 1 ; j++) { int pos = binary_Search(tmp , 1 , k , L[i][j]); L[i][j] = pos; } } //上面几行都是离散化用的 build(); for(i = 1 ; i <= n ; i++) update(L[i][0] , L[i][1] , i , 1 , k , 1); //注意这个地方不用n而是要用k，这个地方卡我1小时 query(1 , k , 1 , k , 1); int res = 0; for(i = 1 ; i <= n ; i++) if(p[i]) res++; printf("%d\n",res); return 0;}
hihocoder 1079 离散化