题意：给n个线段，每个线段会覆盖一些点，求删最少的线段，使得每个点覆盖的线段不超过k条。
思路：按右端点排序，之后依次加入每个线段，查询线段覆盖区间内的每个点，覆盖的最大线段数量，如果不超过k，那就可以直接加入。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; int s[maxn<<2],col[maxn<<2]; struct node { int id,l,r; }p[maxn]; bool cmp(node a,node b) { if(a.r==b.r)return a.l<b.l; else return a.r<b.r; } void up(int p) { s[p]=max(s[p<<1],s[p<<1|1]); } void down(int p,int l,int r) { if(col[p]) { s[p<<1]+=col[p]; s[p<<1|1]+=col[p]; col[p<<1]+=col[p]; col[p<<1|1]+=col[p]; col[p]=0; } } void modify(int p,int l,int r,int x,int y,int c) { if(x<=l&&r<=y) { s[p]+=c; col[p]+=c; return; } down(p,l,r); int mid=l+r>>1; if(x<=mid)modify(p<<1,l,mid,x,y,c); if(y>mid) modify(p<<1|1,mid+1,r,x,y,c); up(p); } int query(int p,int l,int r,int x,int y) { if(x<=l&&r<=y) { return s[p]; } down(p,l,r); int mid=l+r>>1,maxn=0; if(x<=mid)maxn=max(maxn,query(p<<1,l,mid,x,y)); if(y>mid)maxn=max(maxn,query(p<<1|1,mid+1,r,x,y)); return maxn; } int main() { int n,k,ans[maxn]={0},cnt=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].l,&p[i].r); p[i].id=i; } sort(p+1,p+1+n,cmp); for(int i=1;i<=n;i++) { int tmp=query(1,1,maxn,p[i].l,p[i].r); if(tmp<k) modify(1,1,maxn,p[i].l,p[i].r,1),ans[p[i].id]=1,cnt++; } printf("%d ",n-cnt); int cas=0; for(int i=1;i<=n;i++) { if(!ans[i]) { printf("%d",i),cas++; if(cas==n-cnt)printf(" "); else printf(" "); } } return 0; }