/*一开始以为是线段树开小了 后来发现我这种算法最坏时要开到16倍 但不知为何还是RE 自己随机的大数据也没发现问题 RE找不到原因真是太苦了 求助啊 让我改成WA和TLE都行啊
*/

#include <iostream>
#include <fstream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Inf (1<<29)
const int maxn=11111;
struct Line{
	int left,right,col;
}T[maxn<<4];
pair<int,int> data[maxn];
map<int,int> Map;
int tmp[maxn<<2];
bool list[maxn];
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid (left+right>>1)
#define left (T[rt].left)
#define right (T[rt].right)
#define len (right-left+1)
inline void pushdown(int rt){
	T[lson].col=T[rson].col=T[rt].col;
	T[rt].col=0;
}
void build(int l,int r,int rt){
	left=l,right=r;
	T[rt].col=0;
	if(l==r)
		return;
	build(l,mid,lson);
	build(mid+1,r,rson);
}
void update(int l,int r,int c,int rt){
	if(l<=left&&right<=r){
		T[rt].col=c;
		return;
	}
	if(T[rt].col)
		pushdown(rt);
	if(l<=mid)
		update(l,r,c,lson);
        if(r>mid)
		update(l,r,c,rson);		
}
int query(int rt){
	if(T[rt].col){
		if(list[T[rt].col]==false){
			list[T[rt].col]=true;
			return 1;
		}
		return 0;
	}
	if(T[rt].col)
		pushdown(rt);
	return query(lson)+query(rson);
}
int main(){
	int test,n,l,r;
	scanf("%d",&test);
	while(test--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d%d",&data[i].fi,&data[i].se);
		int id=0;
		for(int i=1;i<=n;i++){
			tmp[id++]=data[i].fi
			tmp[id++]=data[i].se;
		}
		sort(tmp,tmp+id);
		int cnt=0;
		Map[tmp[0]]=++cnt;
		for(int i=1;i<id;i++){
			if(tmp[i]==tmp[i-1])
				continue;
			if(tmp[i]!=tmp[i-1]+1)
				++cnt;
			Map[tmp[i]]=++cnt;
		}		
		build(1,cnt,1);
		for(int i=1;i<=n;i++){
			update(Map[data[i].fi],Map[data[i].se],i,1);
		}
		printf("%d\n",query(1));
		Map.clear();
		memset(list,false,sizeof(list));
	}
	return 0;
}

• Re:RE了很久 求助啊 (2289) drn 2012-09-02 17:07:23
  • Re:RE了很久 求助啊 (2032) drn 2012-09-02 17:11:11
    • 测测 0 这组数据 (51) fly2best 2013-03-01 11:01:26
• Re:RE了很久 求助啊 (2289) salvete 2018-08-23 18:37:18