Rt,这是code:
#include <bits/stdc++.h>
#define N 100100
using namespace std;
int color[N],lll[N],rrr[N],x[N],cnt=0;
bool book[N];
void push_down(int rt)
{
if(color[rt]!=-1)
{
color[rt<<1]=color[rt<<1|1]=color[rt];
color[rt]=-1;
}
}
void updata(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
color[rt]=c;
return;
}
push_down(rt);
int mid=(l+r)>>1;
if(L<=mid)
updata(L,R,c,l,mid,rt<<1);
if(R>mid)
updata(L,R,c,mid+1,r,rt<<1|1);
}
void query(int l,int r,int rt)
{
if(color[rt]!=-1)
{
if(!book[color[rt]]) cnt++;
book[color[rt]]=true;
return;
}
if(l==r) return;
int mid=(l+r)>>1;
query(l,mid,rt<<1);
query(mid+1,r,rt<<1|1);
}
int erfen(int k,int n)
{
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(x[mid]==k) return mid;
if(x[mid]<k) l=mid+1;
else r=mid-1;
}
return -1;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
int tot=0;
cnt=0;
memset(color,-1,sizeof(color));
memset(book,false,sizeof(book));
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&lll[i],&rrr[i]);
x[tot++]=lll[i];
x[tot++]=rrr[i];
}
sort(x,x+tot);
int ans=1;
for(int j=1;j<tot;j++)
if(x[j]!=x[j-1])
x[ans++]=x[j];
for(int j=ans-1;j>0;j--)
if(x[j]!=x[j-1]+1)
x[ans++]=x[j-1]+1;
sort(x,x+ans);
for(int i=0;i<n;i++)
{
int l=erfen(lll[i],ans);
int r=erfen(rrr[i],ans);
updata(l,r,i,0,ans,1);
}
query(0,ans,1);
printf("%d\n",&cnt);
}
return 0;
}
样例就是不过,有偿求助!