开始就直接用延迟标记搞了下，最后发现内存肯定会爆了，数据太大了；
问了瓜神，原来应该用离散化来做这题，具体见注释
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 0xfffffff #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 444444 int col[maxn<<2]; int l[maxn],r[maxn]; int q[maxn],q1[maxn],vis[maxn],hash[maxn]; void pushdown(int rt) { if(col[rt]) { col[rt<<1]=col[rt<<1|1]=col[rt]; col[rt]=0; } } void build(int l,int r,int rt) { col[rt]=0; if(l==r) return ; int m=(l+r)>>1; build(lson); build(rson); } void update(int L,int R,int cha,int l,int r,int rt) { if(L<=l&&R>=r) { col[rt]=cha; return ; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,cha,lson); if(R>m) update(L,R,cha,rson); } void query(int l,int r,int rt) { if(col[rt])//如果某张海报存在，将这张海报标记一下 { hash[col[rt]]=1; return ; } int m=(l+r)>>1; query(lson); query(rson); } int bsearch(int key,int *a,int len)//二分查找 { int l=0,r=len-1; while(l<=len) { int m=(l+r)>>1; if(a[m]==key) return m+1; else if(a[m]>key) r=m-1; else l=m+1; } } int main() { int t,n; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); memset(hash,0,sizeof(hash)); scanf("%d",&n); int ans=0,ans1=0; for(int i=1;i<=n;i++) { scanf("%d%d",&l[i],&r[i]); q[ans++]=l[i];q[ans++]=r[i]; } sort(q,q+ans); for(int i=0;i