CF1889C2 Doremy's Drying Plan (Hard Version)

, ,

打比赛的时候完全没有往 dp 上面去想。写完 C1 以为是什么高妙数据结构。大概是晚上糊涂了。

但其实 dp 的转移也挺妙的！

考虑 dp，令 $f_{i,j}$ 表示当前已经选择了 $j$ 天不下雨，$i$ 为当前被覆盖的点。然后钦定从上一个干旱的店转移过来，$f_{i,j}\gets\max f_{k,j-t}+1$。

现在我们要算对于每个 $k$ 所对应的 $t$。考虑所有覆盖 $i$ 的线段集合 $[l_i,r_i]$：

  • $l_i\le k$，因为 $k$ 已经被我们钦定是干旱的了，所以这条线段应该已经在 $f_{k,j-t}$ 已经被去除了，不用算贡献。
  • $l_i>k$，这是我们要新算的。

也就是说 $t=\sum[k<l_i\le i\le r_i]$。

观察到第二维的范围是 $O(K)$ 的，启发我们对于每个 $t$，算出一段区间，然后区间查询最大值。

如果线段树查询的复杂度 $O(nK^2\log n)$ 我们是无法接受的。而每次 dp 只会在序列的最末尾加一个数而且不会修改，用 ST 表维护。不过这个 ST 表是向左的，才可以更新。

复杂度 $O(nK\log n+nK^2)$，分别是更新 ST 表和更新 dp 的复杂度。线段集合可以用 multiset 维护。

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
98
99
100
101
// LUOGU_RID: 135155930
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#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;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int lg[maxn];
const int inf=1e9;
struct ST {
	int f[maxn][21];
	void clear(int n) {
		int i,j;
		for (j=0;j<=20;j++) for (i=0;i<=n;i++) f[i][j]=-inf;
	}
	void insert(int pos,int k) {
		f[pos][0]=k;int j;
		for (j=1;j<=lg[pos+1];j++) 
			f[pos][j]=max(f[pos][j-1],f[pos-(1<<j-1)][j-1]);
	}
	int query(int l,int r) {
		if (l>r) return -inf;
		int z=lg[r-l+1];
		return max(f[r][z],f[l+(1<<z)-1][z]);
	}
}t[11];
int n,m,k,id[maxn],ans;
vector<pair<int,int> >O[maxn];
multiset<int>tr;
int f[maxn][11];
void solve(void) {
	int i,j,l,x,y;ans=0;
	read(n);read(m);read(k);
	tr.clear();
	for (j=0;j<=k;j++) t[j].clear(n);
	for (i=1;i<=n+1;i++) {
		O[i].clear();
		for (j=0;j<=k;j++) f[i][j]=-inf;
	}
	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for (i=1;i<=m;i++) {
		read(x),read(y);
		O[x].push_back(mk(x,1));
		O[y+1].push_back(mk(x,-1));
	}
	t[0].insert(0,0);
	for (i=1;i<=n;i++) {
		for (auto tmp:O[i]) {
			if (tmp.se==1) tr.insert(tmp.fi);
			else tr.erase(tr.lower_bound(tmp.fi));
		}
		auto it=tr.end();
		int tot=k+1;
		for (j=1;j<=k+1;j++) {
			if (it==tr.begin()) {tot=j-1;break;}
			--it;
			id[j]=(*it);
		}
		id[0]=i;
		id[tot+1]=0;
		for (j=0;j<=k;j++) {
			int r=min({k,tot,j});
			for (l=0;l<=r;l++) {
				f[i][j]=max(f[i][j],t[j-l].query(id[l+1],id[l]-1)+1);
			}
		}
		for (j=0;j<=k;j++) ans=max(ans,f[i][j]),t[j].insert(i,f[i][j]);
	}
	printf("%d\n",ans);
}
signed main(void){
	int i,T;
	read(T);
	while (T--) solve();
	return 0;
}