CF1830F 题解

First Post:

Last Update:

分享一个 KTT 做法，并简单介绍一下 KTT。

首先考虑 DP，设 表示最后一个选的点为 的方案数（暂时不计算 的贡献，等到 的下一个点再计算），那么有转移 。

考虑用扫描线解决 的限制，或者说，维护 表示从 转移到当前位置 的代价，那么每次 时，单点修改 为 ，将所有 的区间提出，对于 中的所有 ，将 。转移时取 全局 即可。

整理一下操作：单点修改 ，区间使 ，查询 全局 。

分块维护凸包可以做到 ，但过不了，故不展开。

介绍一下 KTT 这种数据结构（更详细的介绍参见 EI's blog)。

对于每个 而言，其实质上是个一次函数 ，表示该点被区间操作了 次后的真实值。

如果 ，那么我们只需在线段树上维护区间中 的 即可。

如果 ，其实也可以维护 的 ，但是有一个问题在于，可能原本这个区间的 在左儿子，但是进行若干次区间加之后，右儿子中的真实值更大了，这时再沿用原来的结果就会出问题。

KTT 的处理思路就是，对线段树上的每个节点，处理出一个时间阈值 ，表示当前区间加了 次后，该节点或其后代节点中 的取向会发生改变。因为 两边的一次函数都是已知的，时间 容易被处理出来。

对一个节点进行区间加时，如果当前加的值 比 小，那就直接让当前区间维护的一次函数的 加上 ，并更新区间加 tag。否则，就将 加上当前节点的 ，加到两个子区间，然后递归下去，再 pushup 更新当前节点的信息。

复杂度证明详见 EI 的 blog。

基本思想是，如果区间加的次数 极小， 的取向不会发生改变，就用简单方法维护。否则就递归更新，势能分析保证复杂度。

在本题使用 KTT，时间复杂度可以做到 。

代码如下：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 1e6 + 5,Sz = N << 2;
typedef long long ll;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
#define FI first
#define SE second
int n,m,p[N];
int L[N],R[N];
ll dp[N];
vector<int> Qu[N];

struct Func{
	int k;ll b;
	Func() { k = b = 0;}
	Func(const int _k,const ll _b):k(_k),b(_b){}
	Func operator + (const Func &rhs) const { return Func(k + rhs.k,b + rhs.b);}
	void add(int v) { b += 1ll * k * v;} 
};
inline pair<Func,ll> Max(Func a,Func b)
{
	if((a.k < b.k) || (a.k == b.k && a.b < b.b)) swap(a,b);
	if(a.b >= b.b) return make_pair(a,llinf);
	else return make_pair(b,(b.b - a.b) / (a.k - b.k));
}

struct Node{
	Func Mx;
	ll x; // 赶超阈值
	inline friend Node operator + (const Node &a,const Node &b)
	{
		Node res;
		res.x = min(a.x,b.x);
		auto tmp = Max(a.Mx,b.Mx);
		res.Mx = tmp.FI;res.x = min(res.x,tmp.SE);
		return res;
	}
};
Node tr[Sz];
int tag[Sz];
void pushup(int x) { tr[x] = tr[x << 1] + tr[x << 1 | 1];}
inline void Giv(int x,int v)
{
	tag[x] += v;
	tr[x].x -= v;
	tr[x].Mx.add(v);
}
inline void pushdown(int x)
{
	if(!tag[x]) return;
	Giv(x << 1,tag[x]);Giv(x << 1 | 1,tag[x]);
	tag[x] = 0;
}
void defeat(int k,int l,int r,int v)
{
	if(v >= tr[k].x)
	{
		int mid = l + r >> 1;
		int t = tag[k] + v;tag[k] = 0;
		defeat(k << 1,l,mid,t);
		defeat(k << 1 | 1,mid + 1,r,t);
		pushup(k);
	}
	else Giv(k,v);
}
void modify(int k,int l,int r,int x,int y,int v)
{
	if(x <= l && r <= y) return defeat(k,l,r,v);
	int mid = l + r >> 1;
	pushdown(k);
	if(x <= mid) modify(k << 1,l,mid,x,y,v);
	if(mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
	pushup(k);
}
ll Query(int k,int l,int r,int x,int y)
{
	if(x <= l && r <= y) return tr[k].Mx.b;
	int mid = l + r >> 1;
	pushdown(k);
	if(y <= mid) return Query(k << 1,l,mid,x,y);
	else if(x > mid) return Query(k << 1 | 1,mid + 1,r,x,y);
	else return max(Query(k << 1,l,mid,x,y),Query(k << 1 | 1,mid + 1,r,x,y));
}
void Change(int k,int l,int r,int pos)
{
	if(l == r) { 
		Func t(p[pos] + tag[k],dp[pos]);
		tr[k].Mx = t;tr[k].x = llinf;
		return;
	}
	int mid = l + r >> 1;
	pushdown(k);
	if(pos <= mid) Change(k << 1,l,mid,pos);
	else Change(k << 1 | 1,mid + 1,r,pos);
	pushup(k);
}
void build(int k,int l,int r)
{
	tr[k].Mx = Func(0,-llinf);
	tr[k].x = llinf;tag[k] = 0;
	if(l == r) return;
	int mid = l + r >> 1;
	build(k << 1,l,mid);build(k << 1 | 1,mid + 1,r);
}
inline void work()
{
	read(n);read(m);
	for(int i = 1;i <= n;i++) read(L[i]),read(R[i]);
	for(int i = 1;i <= m;i++) Qu[i].clear();
	for(int i = 1;i <= n;i++) Qu[R[i]].push_back(i);
	for(int i = 1;i <= m;i++) read(p[i]),dp[i] = -llinf;
	p[++m] = 0;dp[m] = -llinf;
	build(1,0,m);
	dp[0] = 0;
	Change(1,0,m,0);
	for(int i = 1;i <= m;i++)
	{
		dp[i] = tr[1].Mx.b;
		Change(1,0,m,i);
		for(auto k : Qu[i])
			modify(1,0,m,L[k],R[k],1);
	}
	cout << dp[m] << endl;
}
int main()
{
	int T;
	read(T);
	while(T--) work();
	return 0;
}


≡