以后做双精题请至少先跑个数据。。。输入都不一样。。。
做法就是离散化大力线段树。
记得在x+1和y-1插点 看这个数据：
1000 12
1 100
50 80
80 99
50 98
1 56
100 200
200 300
300 500
500 600
600 1000
260 560
160 580
输出7（自己yy吧yy不了网上大把题解）
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,m; struct query { int x,y; }q[4100000]; int lslen,ls[4100000]; void LSH() { lslen=0; for(int i=1;i<=m;i++) { ls[++lslen]=q[i].x,ls[++lslen]=q[i].y; if(q[i].x+1<q[i].y) ls[++lslen]=q[i].x+1,ls[++lslen]=q[i].y-1; } ls[++lslen]=n; sort(ls+1,ls+lslen+1); lslen=unique(ls+1,ls+lslen+1)-ls-1; for(int i=1;i<=m;i++) q[i].x=lower_bound(ls+1,ls+lslen+1,q[i].x)-ls, q[i].y=lower_bound(ls+1,ls+lslen+1,q[i].y)-ls; n=lower_bound(ls+1,ls+lslen+1,n)-ls; } struct trnode { int l,r,lc,rc,c; }tr[4100000];int trlen; void bt(int l,int r) { int now=++trlen; tr[now].l=l;tr[now].r=r;tr[now].c=-1; tr[now].lc=tr[now].rc=-1; if(l<r) { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); } } void change(int now,int l,int r,int k) { if(tr[now].l==l&&tr[now].r==r){tr[now].c=k;return ;} int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(tr[now].c!=-1) { tr[lc].c=tr[now].c; tr[rc].c=tr[now].c; } if(r<=mid) change(lc,l,r,k); else if(mid+1<=l)change(rc,l,r,k); else change(lc,l,mid,k), change(rc,mid+1,r,k); if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c; else tr[now].c=-1; } bool col[4100000]; void findans(int now,int l,int r) { if(tr[now].c!=-1){col[tr[now].c]=true;return ;} if(l==r)return ; int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(r<=mid) findans(lc,l,r); else if(mid+1<=l)findans(rc,l,r); else findans(lc,l,mid),findans(rc,mid+1,r); } int main() { n=1e7;scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].x,&q[i].y); if(q[i].x>n)i--,m--; if(q[i].y>n)q[i].y=n; } LSH(); trlen=0;bt(1,n); for(int i=1;i<=m;i++)change(1,q[i].x,q[i].y,i); memset(col,false,sizeof(col)); findans(1,1,n); int ans=0; for(int i=1;i<=m;i++) if(col[i]==true)ans++; printf("%d ",ans); return 0; }