P3634 [APIO2012] 守卫

,

Description

https://www.luogu.com.cn/problem/P3634

Solution

之前看了好久交了个差分约束上去，然后WA飞了。

先处理一些简单的情况：

  • $0$ 位置标记扔掉。
  • $1$ 的区间如果存在包含，则大的那个区间扔掉。
  • $l=r$，则这个点一定有。

把包含的去掉以后。一个点必选，表示如果不选这个点则一定无解。

一种合法的最优的贪心就如果这个区间没有被覆盖则贪心的选取这个区间的右端点。也就是说必选点的集合一定是这些右端点的子集。

考虑一个区间 $[l,r]$，在最优方案中我们选取了其右端点 $r$，同样的，次优的方案是选择 $r-1$。算出这种情况下最小的守卫数 $>k$ 则 $r$ 一定要选。记 $f_i$ 表示从左到右覆盖前 $i$ 个区间最少需要选 $f_i$ 个，$g_i$ 表示从右到左。二分出最左边的区间 $l_p\ge r$，必选的充要条件在 $f_i+g_p>k$。

注意特判可以填的位置等于守卫个数的情况。复杂度 $O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2) {
	ll sum=1;x%=mod;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int nex[maxn],las[maxn];
int n,k,m;
int cnt,d[maxn];
struct node {
	int l,r;
}a[maxn];
int f[maxn],g[maxn],stac[maxn],tot;
bool cmp(node x,node y) {return x.l==y.l?x.r>y.r:x.l<y.l;}
signed main(void){
	freopen("1.in","r",stdin);
	int i,op,l,r,nums=0;
	read(n);read(k);read(m);
	while (m--) {
		read(l);read(r);read(op);
		if (op==0) d[l]++,d[r+1]--;
		else a[++cnt]=(node){l,r};
	}
	for (i=1;i<=n;i++) d[i]+=d[i-1],nums+=(d[i]==0);
	nex[n+1]=n+1;
	if (nums==k) {
		for (i=1;i<=n;i++) if (d[i]==0) printf("%d\n",i);
		return 0;
	}
	// gdb(d[99]);
	for (i=1;i<=n;i++) if (!d[i]) las[i]=i;else las[i]=las[i-1];
	for (i=n;i>=1;i--) if (!d[i]) nex[i]=i;else nex[i]=nex[i+1];
	// for (i=1;i<=n;i++) gdb(i,d[i],las[i],nex[i]);
	for (i=1;i<=cnt;i++) a[i].l=nex[a[i].l],a[i].r=las[a[i].r];
	sort(a+1,a+1+cnt,cmp);
	for (i=1;i<=cnt;i++) {
		if (a[i].l>a[i].r) continue;
		while (tot&&a[stac[tot]].r>=a[i].r) tot--;
		stac[++tot]=i;
	}
	cnt=tot;
	for (i=1;i<=tot;i++) a[i]=a[stac[i]];
	// for (i=1;i<=tot;i++) gdb(a[i].l,a[i].r);
	int now=0;
	for (i=1;i<=tot;i++) {
		if (now<a[i].l) f[i]=f[i-1]+1,now=a[i].r;
		else f[i]=f[i-1];
	} 
	now=n+1;
	for (i=tot;i>=1;i--) {
		if (now>a[i].r) g[i]=g[i+1]+1,now=a[i].l;
		else g[i]=g[i+1];
	}
	int flag=0;
	for (i=1;i<=tot;i++) {
		int p,l=0,r=tot+1,mid;
		// gdb(a[i].l,a[i].r);
		if (a[i].l==a[i].r) {flag=1;printf("%d\n",a[i].l);continue;}
		if (f[i]!=f[i-1]+1) continue;
		while (l+1<r) {
			mid=l+r>>1;
			if (a[mid].l>=a[i].r) r=mid;
			else l=mid; 
		}
		// assert(r>i);
		// gdb(i,r,f[i],g[r]);
		if (f[i]+g[r]>k) {flag=1;printf("%d\n",a[i].r);continue;}
	}
	if (!flag) puts("-1");
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i