1. 首页
2. 线段树
3. 本页

Poj 2528 Mayor's posters (成段更新+离散化)

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
线段树功能:update:成段替换 query:简单 hash
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]
我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我
只需要 1000,1990,2000,2012 就够了,将其分别映射到 0,1,2,3,在于复杂度就大大的
降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到 1~n,这样复杂度就会小
很多很多
1～10  1～4  6～10
对于这种案例，如果直接离散化X[1]=1,X[2]=4,X[3]=6,X[4]=10
计算的结果就会出现错误～
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于 1 的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然
后再做线段树就好了.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN = 105500;

int tree[MAXN << 2];
int col[MAXN << 2];
bool hash[MAXN];
int ls[MAXN << 2];
int li[MAXN];
int ri[MAXN];
int ans;

inline void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

inline void pushdown(int rt) {
	if (col[rt] != -1) {
		col[rt << 1] = col[rt << 1 | 1] = col[rt];
		col[rt] = -1;
	}
}

void build(int l, int r, int rt) {
	col[rt] = -1;
	if (l == r) {
		tree[rt] = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}

void update(int L, int R, int fg, int l, int r, int rt) {
	if (L <= l && r <= R) {
		col[rt] = fg;
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if (L <= m) {
		update(L, R, fg, lson);
	}
	if (R > m) {
		update(L, R, fg, rson);
	}
}
void query(int l, int r, int rt) {
	if (l == r)
	{
		if (col[rt] != -1) {
			if (!hash[col[rt]]) {
				ans++;
			}
			hash[col[rt]] = 1;
		}
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	query(lson);
	query(rson);
}

int get(int x, int n) {
	int l = 0, r = n;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (ls[m] == x) {
			return m;
		}
		if (ls[m] < x) {
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
}

int main() {
	int t;
	int n;
	cin >> t;
	while (t--) {
		scanf("%d", &n);
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%d%d", &li[i], &ri[i]);
			ls[cnt++] = li[i];
			ls[cnt++] = ri[i];
		}
		sort(ls, ls + cnt);
		cnt = unique(ls, ls + cnt) - ls;
		for (int i = cnt - 2; i >= 0; i--) {
			if (ls[i + 1] != ls[i] + 1) {
				ls[cnt++] = ls[i] + 1;
			}
		}
		sort(ls, ls + cnt);
		build(0, cnt - 1, 1);
		for (int i = 0; i < n; ++i) {
			int lsl = get(li[i], cnt - 1);
			int lsr = get(ri[i], cnt - 1);
			//cout<<lsl<<" "<<lsr<<endl;
			update(lsl, lsr, i, 0, cnt - 1, 1);
		}
		memset(hash, false, sizeof(hash));
		ans = 0;
		query(0, cnt - 1, 1);
		printf("%d\n", ans);

	}

	return 0;
}