题目链接：
代码：
#include#include #include #include #include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define maxn 100050using namespace std;int cnt[maxn<<1];int v[maxn<<2];int vis[maxn<<2]={0};int modify[maxn][2];int ans=0;void travel(int l,int r,int rt){ if(v[rt]) { if(!vis[v[rt]]) vis[v[rt]]=1,ans++; return; } if(l==r) return; int m=(l+r)>>1; travel(lson); travel(rson);}void update(int L,int R,int w,int l,int r,int rt){ if(L<=l&&R>=r) { v[rt]=w; return; } if(v[rt]) { v[rt<<1|1]=v[rt<<1]=v[rt]; v[rt]=0; } int m=(l+r)>>1; if(L<=m) update(L,R,w,lson); if(R>m) update(L,R,w,rson);}int main(){// freopen("in.txt","r",stdin); int d,n,a,b,s=0; scanf("%d%d",&d,&n); for(int i=1; i<=d; i++) { scanf("%d%d",&modify[i][0],&modify[i][1]); cnt[s++]=modify[i][0]; cnt[s++]=modify[i][1]; } sort(cnt,cnt+s); s=unique(cnt,cnt+s)-cnt; for(int i=1; i<=d; i++) { a=lower_bound(cnt,cnt+s,modify[i][0])-cnt+1; // x~x+1 才代表线段树中的一个点 b=lower_bound(cnt,cnt+s,modify[i][1])-cnt; update(a,b,i,1,s,1); } travel(1,s,1); printf("%d\n",ans); return 0;}