#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 200002;
int col[MAXN * 10], hash[MAXN], tt[MAXN * 2], ST[MAXN], ED[MAXN], Ncol[MAXN], tot;
bool used[MAXN];
inline int rehash(int num)
{
	int l = 1, r = tot;
	while (l <= r){
		int m = (l + r) >> 1;
		if (hash[m] == num) return m;
		if (hash[m] < num) l = m + 1; else r = m - 1;
		}
	return l;
}
void insert(int idx, int ll, int rr, int l, int r, int color)
{
	if (l <= ll && r >= rr){
		col[idx] = color; return;
		}
	if (col[idx] != 0){
		col[idx * 2] = col[idx * 2 + 1] = col[idx]; col[idx] = 0;
		}
	int mid = (ll + rr) >> 1;
	if (l < mid) insert(idx * 2, ll, mid, l, r, color);
	if (r > mid) insert(idx * 2 + 1, mid, rr, l, r, color);
} 
void rebuild(int idx, int l, int r)
{
	if (l + 1 == r){
		Ncol[l] = col[idx];
		return;
		}
	if (col[idx] != 0){
		col[idx * 2] = col[idx * 2 + 1] = col[idx]; col[idx] = 0;
		}
	int mid = (l + r ) >> 1;
	rebuild(idx * 2, l, mid);
	rebuild(idx * 2 + 1, mid, r);
}
int main()
{
int TEST; scanf("%d", &TEST);
while(TEST--){
	memset(col, 0, sizeof(col));
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &ST[i], &ED[i]);
	for (int i = 1; i <= n; i++) ++ED[i];
	for (int i = 1; i <= n; i++) tt[i * 2 - 1] = ST[i], tt[i * 2] = ED[i];
	sort(tt + 1, tt + 2 * n + 1); hash[tot = 1] = tt[1];
	for (int i = 2; i <= 2 * n; i++) if (tt[i] != tt[i - 1]) hash[++tot] = tt[i];
	for (int i = 1; i <= n;  i++) 
		insert(1, 1, tot, rehash(ST[i]), rehash(ED[i]), i);
	rebuild(1, 1, tot);
	memset(used, 0, sizeof(used)); memset(Ncol, 0, sizeof(Ncol));
	for (int i = 1; i <= tot; i++) used[Ncol[i]] = true;
	int ans = 0;
	for (int i = 1; i <= n; i++) ans+= used[i];
	printf("%d\n", ans);
}
}
	

• Re:建议管理员检查一下数据，部分错误的离散化无法AC，正确的离散化无法AC，谢谢，附WA程序 (34) wwwaaannngggrs 2011-04-07 00:18:10