poj 3468 A Simple Problemwith Integers[セグメントツリー]
2137 ワード
ここ数日作った線分の木を全部貼って...hhについて行ったことを表す.
ポスターを贴って、、、やはり1段更新します.
範囲が少し広く、離散化操作が行われている.
最后に何枚か见える、クエリー..
参照先:
ポスターを贴って、、、やはり1段更新します.
範囲が少し広く、離散化操作が行われている.
最后に何枚か见える、クエリー..
参照先:
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 40005
int li[maxn],ri[maxn];
int res[maxn*3];//
int col[maxn<<4];
bool hash[maxn];
int cnt;
int cmp(const void *a , const void *b){return *(int *)a - *(int *)b;}
void pushdown(int rt){
if(col[rt]!=-1){
col[rt<<1]=col[rt<<1|1]=col[rt];
col[rt]=-1;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(l>=L&&r<=R){
col[rt]=c;
return ;
}
pushdown(rt);
int m=(l+r)>>1;
if(L<=m) update(L,R,c,lson);
if(R>m) update(L,R,c,rson);
}
int bin(int key,int n,int res[]){
int l=0;
int r=n-1;
while(l<=r){
int m=(l+r)>>1;
if(res[m]==key) return m;
if(key<=res[m]) r=m-1;
else l=m+1;
}
return -1;
}
void query(int l,int r,int rt){
if(col[rt]!=-1){
if(!hash[col[rt]]) cnt++;
hash[col[rt]]=true;
return;
}
if(l==r) return ;
int m=(l+r)>>1;
query(lson);
query(rson);
}
int main(){
int T;
int n,m;
scanf("%d",&T);
m=0;
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&li[i],&ri[i]);
res[m++]=li[i];
res[m++]=ri[i];
}
qsort(res,m,sizeof(res[0]),cmp);
int t=1;
for(int i=1;i<m;i++)
if(res[i]!=res[i-1])
res[t++]=res[i];
for(int i=t-1;i>0;i--){
if(res[i]!=res[i-1]+1)
res[t++]=res[i-1]+1;
}
qsort(res,t,sizeof(res[0]),cmp);
memset(col,-1,sizeof(col));
for(int i=0;i<n;i++){
int l=bin(li[i],t,res);
int r=bin(ri[i],t,res);
update(l,r,i,0,t,1);
}
cnt=0;
memset(hash,false,sizeof(hash));
query(0,t,1);
printf("%d
",cnt);
}
return 0;
}