点击这里查看原题
思路比较复杂，细节也很多，具体的讲解写在代码的注释里好了
/* User:Small Language:C++ Problem No.:2811 */ #include<bits/stdc++.h> #define ll long long #define inf 999999999 #define pii pair<int,int> #define mp make_pair using namespace std; const int M=1e5+5; int sum[M],n,k,m,cnt,f[M],g[M],pre[M],nex[M],p[M],id[M],top,ql[M],qr[M]; bool vis[M]; vector<pii> a,b; int main(){ freopen("data.in","r",stdin);// ios::sync_with_stdio(false); scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=m;i++){ int l,r,op; scanf("%d%d%d",&l,&r,&op); if(op==0){//给没有忍者的区间+1 sum[l]++; sum[r+1]--; } else a.push_back(mp(l,r)); } for(int i=1;i<=n;i++){ sum[i]+=sum[i-1];//做差分，若sum[i]==0则代表i位置有可能有忍者 if(sum[i]==0){ p[++cnt]=i; id[i]=cnt; } } if(cnt==k){//特判，如果可能有忍者的点的数量等于忍者的数量，直接输出所有可能的点 for(int i=1;i<=cnt;i++) printf("%d\n",p[i]); return 0; } for(int i=1;i<=n;i++) pre[i]=id[i]?id[i]:pre[i-1];//pre[i]表示在i之前的距离i最近的点的编号（如果i位置有点，那么pre[i]就是这个位置的点的编号） nex[n+1]=inf; for(int i=n;i;i--) nex[i]=id[i]?id[i]:nex[i+1];//nex[i]同理 int asize=a.size(); for(int i=0;i<asize;i++){ int l=a[i].first,r=a[i].second; l=nex[l]; r=pre[r];//l,r是将原区间两端的无忍者部分删去后的区间，用区间两端点的编号表示 if(l>r) continue; b.push_back(mp(l,r)); } sort(b.begin(),b.end()); int bsize=b.size(); for(int i=0;i<bsize;i++){ while(top&&b[i].second<=qr[top]) top--;//去除所有有包含关系的区间，因为如果有大区间包含小区间，只要满足小区间，大区间就满足了 ql[++top]=b[i].first,qr[top]=b[i].second; } int mx=0,mn=inf; for(int i=1;i<=top;i++) if(ql[i]>mx) f[i]=f[i-1]+1,mx=qr[i];//f[i]表示前i个区间最少的忍者数，贪心的想每次将忍者放在区间的右端点即可 else f[i]=f[i-1]; for(int i=top;i;i--) if(qr[i]<mn) g[i]=g[i+1]+1,mn=ql[i];//g[i]表示后i个区间最少的忍者数 else g[i]=g[i+1]; bool flag=0; for(int i=1;i<=top;i++){ if(f[i]!=f[i-1]+1) continue; if(ql[i]==qr[i]){//区间长度为1，直接输出 flag=1; printf("%d\n",p[ql[i]]); continue; } int x=qr[i]-1,t1=0,t2=top+1,l,r;//判断区间右端点-1的位置能不能放，如果不能放，说明区间右端点的位置必须放 l=1,r=i-1; while(l<=r){//找出x左边的最近区间 int mi=l+r>>1; if(qr[mi]<x) t1=mi,l=mi+1; else r=mi-1; } l=i+1,r=top; while(l<=r){//找出x右边的最近区间 int mi=l+r>>1; if(ql[mi]>x) t2=mi,r=mi-1; else l=mi+1; } if(f[t1]+g[t2]+1>k){//x位置不能放，于是x+1位置必须放 flag=1; printf("%d\n",p[x+1]); } } if(!flag) puts("-1"); return 0; }