题目链接：POJ2528
【题意】给出n条区间，每次覆盖区间上的颜色，每条区间颜色不同，且按照给出的顺序覆盖区间，求最后一共有多少种颜色，初始没有颜色。
【分析】首先肯定想到线段树，维护区间信息col，用-1代表没有颜色，0代表有多种颜色，>0代表只有一种颜色;由于最后只需要查询一次，所以可以用O(n)的查询线段树，碰到>0时标记出现的颜色，混合色的全部查询下去；
然后由于区间值很大，需要离散，但是如果直接把所有左右区间排序离散会使得区间之间的距离体现不出来而出错(虽然POJ没有这样的数据)，例如[1,10] [1,3] [6,10]离散之后是[0,3] [0,1] [2,3]这样本来的答案是3，这里成了2，因为忽略了区间之间的距离关系；
解决办法：我是保存排序之后的各个点，然后二分查询下标，利用一个sum[]保存他们之间额外的空位，如果这个点和前一个之间原本的差值>1则需要让他们之间留出一个空位，所以sum[i] = sum[i-1]+1，否则不留空位sum[i] = sum[i-1];这样就区分出他们的相对距离了；
【AC CODE】141ms
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define id(x,y) ((x)+(y)|(x)!=(y))
const int INF = 0x3f3f3f3f, MAXN = 40000+10, MOD = 1000007;
struct HASH{
int head[MOD], next[MAXN], sum[MAXN], cnt, node[MAXN];
void clear(){
cnt = 0;
clc(head,-1);
clc(sum,0);
}
int hash(int s){
return s%MOD;
}
void insert(int s){
int id = hash(s);
int u = head[id];
while(~u){
if(s == node[u])
{
sum[u]++;
return;
}
u = next[u];
}
sum[cnt] = 1;
node[cnt] = s;
next[cnt] = head[id];
head[id] = cnt++;
}
int find(int s){
int id = hash(s);
int u = head[id];
while(~u){
if(node[u] == s) return sum[u];
u = next[u];
}
return 0;
}
}use;
int col[MAXN<<1];//-1代表没颜色，0混合色，>0单一颜色
int set[MAXN<<1], cnt;//set-lazy标记
int a[MAXN],b[MAXN], s[MAXN<<1];
void push_up(int x, int y, int m)
{
int u = id(x,y), l = id(x,m), r = id(m+1,y);
if(col[l] == col[r]) col[u] = col[l];
else col[u] = 0;
}
void push_down(int x, int y, int m)
{
int u = id(x,y), l = id(x,m), r = id(m+1,y);
if(~set[u])
{
col[l] = col[r] = set[u];
set[l] = set[r] = set[u];
set[u] = -1;
}
}
int ql,qr,v;
void update(int x, int y)
{
if(ql <= x && y <= qr)
{
col[id(x,y)] = v,set[id(x,y)] = v;
return;
}
int m = (x+y)>>1;
push_down(x,y,m);
if(ql <= m) update(x,m);
if(qr > m) update(m+1,y);
push_up(x,y,m);
}
bool vis[MAXN];
void query(int x, int y)
{
int u = id(x,y);
if(-1 == col[u]) return;
if(col[u] > 0)
{
vis[col[u]] = true;
return;
}
int m = (x+y)>>1;
push_down(x,y,m);
query(x,m);
query(m+1,y);
}
void add_num(int w)
{
if(!use.find(w))
{
use.insert(w);
s[cnt++] = w;
}
}
int sum[MAXN<<1];
int get_id(int w)
{
int id = lower_bound(s,s+cnt,w)-s;
return id+sum[id];
}
int main()
{
#ifdef SHY
freopen("e:\\1.txt", "r", stdin);
#endif
int t;
scanf("%d%*c", &t);
while(t--)
{
int n;
scanf("%d%*c", &n);
clc(col,-1);
clc(set,-1);
use.clear();
cnt = 0;
repe(i,1,n)
{
scanf("%d %d%*c", &a[i], &b[i]);
add_num(a[i]), add_num(b[i]);
}
sort(s,s+cnt);
rep(i,1,cnt)
{
if(s[i]-s[i-1] > 1) sum[i] = sum[i-1]+1;
else sum[i] = sum[i-1];
}
int mx = cnt+sum[cnt-1];
repe(i,1,n)
{
ql = get_id(a[i]), qr = get_id(b[i]);
v = i;
update(0,mx-1);
}
clc(vis,0);
query(0,mx-1);
int ans = 0;
repe(i,1,n) if(vis[i]) ans++;
printf("%d\n", ans);
}
return 0;
}
/*
5
3
1 10
1 3
6 10
3
5 6
4 5
6 8
5
1 4
2 6
8 10
3 4
7 10
5
1 4
2 6
8 10
3 4
7 10
4
2 4
3 5
1 3
5 7
==================
3
2
4
4
3
*/
