POJ 2528(线段树+离散化)

求出最后还能看见多少张海报。(题意是我抄的...)

思路：

能够想到用线段树去进行区间更新，求最终的更新结果。但发现给的数据会得到1000万，所以普通的线段树是开不了的，但是发现n的范围为1万，可以在这上面做点文章，所以可以对这给定的n个区间进行离散化。

普通离散化的具体步骤为：对所有输入的数排序，然后进行去重，然后将数映射到1~n。

但是普通离散化在本题中是不可行的，我们注意到，每个数字其实表示的是一个单位长度(一个点也是一段)，举个栗子：

1-10 1-4 6-10  直接进行算得到的ans是3

进行离散化：X[1] = 1, X[2] = 4, X[3] = 6, X[4] = 10

1-4 1-2 3-4    计算得到ans为2，结果错误！

怎么解决呢？如果相邻数字间距大于1的话, 在其中加上任意一个中间数字, 比如上面例子会加成[1, 3, 4, 5, 6, 7, 10], 然后再做线段树就ok，这样做可以防止丢失单点的成段效果。

具体代码实现如下:

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <set>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
const int maxn = 10005;
int col[maxn<<4], lazy[maxn<<4];
int inp[maxn][2], chg[maxn<<2];
set<int> hash;	//记录访问过与否 
void pushDown(int rt)
{
	if(lazy[rt])
	{
		lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
		col[rt<<1] = col[rt<<1|1] = lazy[rt];
		lazy[rt] = 0;
	}
}
void build(int l, int r, int rt)
{
	lazy[rt] = 0;
	col[rt] = 0;
	if(l == r) return;
	int m = (l+r) >> 1;
	build(lson);
	build(rson);
}
void update(int k, int L, int R, int l, int r, int rt)
{
	if(L <= l && R >= r)
	{
		col[rt] = k;
		lazy[rt] = k;
		return;
	}
	pushDown(rt);
	int m = (l+r) >> 1;
	if(L <= m) update(k, L, R, lson);
	if(R > m) update(k, L, R, rson); 
}
int query(int l, int r, int rt)
{
	if(l == r) 
	{
		if(col[rt] && !hash.count(col[rt]))
		{
			hash.insert(col[rt]);
			return 1;
		}
		return 0;
	}
	pushDown(rt);
	int m = (l+r) >> 1;
	return query(lson) + query(rson);
}
int main()
{
	int t, n, l, r, cnt;
	scanf("%d", &t);
	for(int i = 1; i <= t; ++i)
	{
		hash.clear(); cnt = 0;
		scanf("%d", &n);
		for(int j = 1; j <= n; ++j)
		{
			scanf("%d %d", &inp[j][0], &inp[j][1]);
			chg[cnt++] = inp[j][0];
			chg[cnt++] = inp[j][1];
		}
		sort(chg, chg+cnt);
		cnt = unique(chg, chg+cnt) - chg;
		int tmp = cnt;
		for(int j = 1; j < tmp; ++j)
		{
			if(chg[j] - chg[j-1] > 1) chg[cnt++] = chg[j-1]+1;
		}
		sort(chg, chg+cnt);
		build(1, cnt, 1);
		for(int j = 1; j <= n; ++j)
		{
			int a = lower_bound(chg, chg+cnt, inp[j][0]) - chg;
			int b = lower_bound(chg, chg+cnt, inp[j][1]) - chg;
			++a, ++b;
			update(j, a, b, 1, cnt, 1);
		}
		printf("%d\n", query(1, cnt, 1));
	}
	return 0;
}

在这儿再补充一下知识点。

1.unique函数

unique()函数是STL中得一个去重函数，在头文件<algorithm>中，unique的功能是去除相邻的重复元素(只保留一个),还有一个容易忽视的特性是它并不真正把重复的元素删除。
unique(num, num+n)返回的是num去重后的尾地址，之所以说比是真正把重复的元素删除，其实是，该函数把重复的元素移到后面去了，依然保存到了原数组中，然后返回去重后的最后一个元素的下一地址。因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。

2.离散化主要代码

sort(num, num+cnt);//排序 
cnt = unique(num, num+cnt) - num;//去重 
for(int i = 1; i <= m; ++i)
{
	int k = lower_bound(num, num+cnt, input[i]) - num;
	//取对应的值在数组中的位置以对应离散值 
	++k;
	//通常使k++,另第一个离散值为1
	//同理也可通过离散值在数组中找到原数值 
}

继续加油~