傻逼线段树。。一开始内存开小了。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define maxn 50500 using namespace std; int t,n,tot=0,root,x[maxn],y[maxn],ans=0,hash[maxn],cnt=0,len=0; bool vis[maxn]; int ls[maxn<<2],rs[maxn<<2],lazy[maxn<<2]; void build(int &now,int left,int right) { now=++tot; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); return; } void modify(int now,int left,int right,int l,int r,int x) { if ((left==l) && (right==r)) { lazy[now]=max(lazy[now],x); return; } int mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,x); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,x); else { modify(ls[now],left,mid,l,mid,x); modify(rs[now],mid+1,right,mid+1,r,x); } return; } int ask(int now,int left,int right,int pos) { if ((left==right) && (left==pos)) return lazy[now]; int mid=(left+right)>>1; if (pos<=mid) return max(ask(ls[now],left,mid,pos),lazy[now]); else return max(ask(rs[now],mid+1,right,pos),lazy[now]); } void work() { memset(vis,false,sizeof(vis)); memset(lazy,0,sizeof(lazy)); cnt=0;tot=0;len=0;ans=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]); hash[++cnt]=x[i];hash[++cnt]=y[i]; } sort(hash+1,hash+cnt+1); len=unique(hash+1,hash+cnt+1)-hash-1; build(root,1,len); for (int i=1;i<=n;i++) { int l=lower_bound(hash+1,hash+len+1,x[i])-hash; int r=lower_bound(hash+1,hash+len+1,y[i])-hash; modify(root,1,len,l,r,i); } for (int i=1;i<=len;i++) vis[ask(root,1,len,i)]=true; for (int i=1;i<=n;i++) if (vis[i]) ans++; printf("%d ",ans); } int main() { scanf("%d",&t); for (int i=1;i<=t;i++) work(); return 0; }