P3634 [APIO2012] 守卫 题解
by_chance
·
·
题解
题意：长为 n 的 01 数列中有 k 个 1，满足 m 个条件。每个条件形如 a_i,b_i,c_i，含义如下：
保证初始有解。求所有必定为 1 的位置。
------------
首先解决简单情况：
1. 丢掉所有条件给出为 $0$ 的位置。
2. 如果剩下的可能位置数与总数相同，剩下的所有位置都满足条件。
3. 如果有某个 $c_i=1$ 的区间长为 $1$，这个位置满足条件。
4. 如果有某两个 $c_i=1$ 的区间有包含关系，只用考虑小的那个。
下面来考虑剩下的情形。对所有区间按左端点递增排序，则右端点也递增。
首先可以贪心求出一组解（不考虑 $k$），这只要从左到右扫描所有区间，如果某个区间还没有 $1$，在其右端点放 $1$。同时可以求出满足前 $i$ 个区间所需要的 $1$ 的数目的最小值 $f_i$。类似的，可以求出满足后 $i$ 个区间所需要的 $1$ 的数目的最小值 $g_i$。
“某个位置必须是 $1$”等价于“某个位置是 $0$ 时无解”。只用考虑那些满足 $f_i = f_{i-1} + 1$ 的区间 $[a_i,b_i]$ 的右端点，记为 $x$。则满足前 $i$ 个区间的条件需要 $f_i$ 个 $1$。
再考虑所有完全在 $x-1$ 右侧的区间，设为后 $p$ 个。假设 $x$ 不是 $1$，所以满足前 $i$ 个区间时不会满足后 $p$ 个区间中的任何一个。那么无解的充分必要条件就是 $f_i + g_p \gt k$。
$p$ 可以二分求。时间复杂度 $O(n \log n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,m,d[N],t,h[N],lst[N],nxt[N],cnt,st[N],top,f[N],g[N],flag;
struct range{int l,r;}p[N];
bool operator <(const range &a,const range &b){
return a.l!=b.l?a.l<b.l:a.r<b.r;
}
int main(){
scanf("%d%d%d",&n,&k,&m);
for(int i=1,a,b,c;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
if(c==0)++d[a],--d[b+1];
else{++t;p[t].l=a;p[t].r=b;}
}
for(int i=1;i<=n;i++){
d[i+1]+=d[i];
if(!d[i]){lst[i]=nxt[i]=++cnt;h[cnt]=i;}
}
if(k==cnt){
for(int i=1;i<=cnt;i++)printf("%d\n",h[i]);
printf("\n");
return 0;
}
for(int i=1;i<=n;i++)if(!lst[i])lst[i]=lst[i-1];
for(int i=n;i>=1;i--)if(!nxt[i])nxt[i]=nxt[i+1];
for(int i=1;i<=t;i++)p[i].l=nxt[p[i].l],p[i].r=lst[p[i].r];
sort(p+1,p+t+1);top=0;
for(int i=1;i<=t;i++){
if(p[i].l>p[i].r)continue;
while(top&&p[st[top]].r>=p[i].r)--top;
st[++top]=i;
}t=top;
for(int i=1;i<=t;i++)p[i]=p[st[i]];
int mx=0,mn=1e9;
for(int i=1;i<=t;i++){
if(p[i].l>mx)f[i]=f[i-1]+1,mx=p[i].r;
else f[i]=f[i-1];
}
for(int i=t;i>=1;i--){
if(p[i].r<mn)g[i]=g[i+1]+1,mn=p[i].l;
else g[i]=g[i+1];
}
for(int i=1;i<=t;i++){
if(p[i].l==p[i].r){flag=1;printf("%d\n",h[p[i].l]);continue;}
if(f[i]!=f[i-1]+1)continue;
int pos=t+1,l=i+1,r=t;
while(l<=r){
int mid=l+r>>1;
if(p[mid].l>p[i].r-1)pos=mid,r=mid-1;
else l=mid+1;
}
if(f[i]+g[pos]>k){flag=1;printf("%d\n",h[p[i].r]);}
}
if(!flag)printf("-1\n");
return 0;
}
```