【训练记录】6.2 训练笔记

记录一下今天的三场比赛,又懒得搬题面了。

如果想要题面可以 QQ 戳我,我觉得你可爱就给你啦。

A.M.

A

秒掉了。大概是考虑从值域 $m$ 开始倒着加数,LIS就一定不会锅。最后判一下序列是否恰好有 $n$ 个元素即可。

「My-Code」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int b[N] ;
vint ans ;
int n, m, k ;

int main(){
cin >> n >> m >> k ; int t = n, s ;
for (int i = 1 ; i <= k ; ++ i) b[i] = qr() ;
for (int i = 1 ; i <= k ; ++ i){
s = m ;
while (t > k - i + 1 && s > b[i])
ans.p_b(s --), t -- ;
ans.p_b(b[i]) ; -- t ;
}
if (ans.size() < n) return puts("No"), 0 ;
puts("Yes") ; for (auto o : ans) printf("%d ", o) ;
return 0 ;
}

B

又秒掉了。大概是考虑倒着枚举每个度数和 $k$,去 check 答案是否合法。check 的时候考虑模拟一个类似 SPFA 的过程,只不过松弛从「边权」转成了「度数和」。根据玄学理论,这个过程应该也会是 $O(Km)$ 的,其中 $K$ 是某个不大的常数。那么最后复杂度大概就是 $O(nKm)$ 附近,可以通过此题。

然而自己用了一个堆维护度数。感觉这样才可以保证复杂度是对的,于是复杂度就大概降为了比较稳的 $O(n^2\log n)$ 左右?

然后剪了一下枝,大概是说考虑每次度数和从 $2\times \max\{\deg_x\}$ 开始枚举而不从 $2\times n$ 开始。实测这样总用时可以快 $15$ 倍。

「My-Code」
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
int _up ;
int n, m ;
int tmp[N] ;
int deg[N] ;
int A[N][N] ;

vint E[N] ;
bool vis[N] ;

struct comp{
bool operator ()(int A, int B){
return tmp[A] < tmp[B] ;
}
};

priority_queue <int, vector<int>, comp> q ;

int main(){
cin >> n >> m ; int u, v ;
for (int i = 1 ; i <= m ; ++ i){
u = qr(), v = qr() ;
deg[u] ++, deg[v] ++ ;
A[u][v] = A[v][u] = 1 ;
chkmax(_up, deg[u] << 1) ;
chkmax(_up, deg[v] << 1) ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
if (!A[i][j] && i != j) E[i].p_b(j), E[j].p_b(i) ;
for (int ans = _up ; ans >= 0 ; -- ans){
int res = m, s = 1 ;
for (int i = 1 ; i <= n ; ++ i){
tmp[i] = deg[i] ;
vis[i] = 1, q.push(i) ;
}
for (int i = 1 ; i <= n ; ++ i)
for (auto j : E[i]) A[i][j] = 0 ;
// debug(ans) ;
while (q.size()){
int x = q.top() ;
// cout << x << ' ' ;
q.pop() ; vis[x] = 0 ;
for (auto y : E[x]){
if (A[x][y]) continue ;
if (tmp[y] + tmp[x] >= ans){
++ res ;
tmp[y] ++, tmp[x] ++ ;
A[x][y] = A[y][x] = 1 ;
if (!vis[y]) q.push(y) ;
}
}
}
// debug(res) ;
if (res == n * (n - 1) / 2)
return cout << ans << " ", 0 ;
}
return 0 ;
}

C

$n,q\le 10^5,m\leq 5$ 。

本以为可以迅速过掉这一场,然后就 被 狙 了。

【论我是如何被狙击的】

自己一开始想了一个 bitset 的做法觉得很稳,复杂度大概是什么 $O\left(q\log n +\dfrac{n\cdot q\cdot m}{w}\right)$ 。大概思路就是考虑拿 bitset 维护当前询问点会被这些线段遮住的点的并集,最后 n-ans.count() 就是答案。

然后,第一个版本是这么写的:维护的时候考虑把所有点按照横坐标排个序,假设某条线段的端点是 $A$,当前询问点是 $O$,某个可能会被挡住的点是 $B$,然后考虑拿叉积去二分出第一个使得 $\overrightarrow{OA}\times \overrightarrow{OB}$ 小于或者大于 $0$ 的点(取决于左右端点)。

写完之后寻思了一下发现不对。因为考虑线段左端点的时候,要按照 $y$ 坐标从小到大排序才能对,而考虑右端点的时候则是要反过来排序。然后改了改觉得很稳。

然后又错了,因为如果某个点的横坐标在某线段的左端点的外部,和内部的处理方式要反!过!来!然后写了个分类讨论觉得很稳。

然后又挂了 ,调了一会儿发现这么判没法解决完全位于某条线段之下的点。于是就预处理了一波和答案或起来,觉得很稳。

然后调了半天还是过不去…突然醒悟,我拿 bitset,维护的是点的绝对顺序,但是如果左端点和右端点,一个是用正着排序二分的,一个使用反着排序二分的,就因为顺序不同而不!能!直!接!合!并!所以这东西就需要写一个映射,但是如果映射的话这不单次询问复杂度又变成 $O(n)$ 了吗!?然后就 GG 了。选择写 $20$ 分暴力滚粗。

然后被 std 秀了一脸= =。


考虑正经做法,还是找性质。考虑具象化一下某个点不能看到某个点的条件,考虑这样

然后就是设从左至右四个与 $x$ 轴的交点分别为 $W,X,Y,Z$ ,那么当且仅当 $W <X$ 且 $Y<Z$ 时,也就是观测点与该线段端点的连线与 $x$ 轴的交点被上方某被观测点与该线段端点的连线与 $x$ 轴的交点完全包含时,当前被观测点会被统计到。

同时,还有一个更强的性质。就是如果当前观测点满足 $YW$ ,那么另一半的条件必然也满足。

以上都是比较显然的。然后考虑这样的话就可以直接暴力容斥了。具体的,先预处理出对于每个线段集合,每个上方的点与该集合内线段的连线与 $x$ 轴所交的区间的。然后对于当前集合下每个点得出的 $l,r$ 分别排序,询问就可以暴力二分出位置来做了。

实现上有点细节。大概是什么 $l$ 要 lower_bound ,$r$ 要 upper_bound 之类的东西。

然后,这题,他卡!精!度!直接开 long double 啥事没有。

「瞎写的
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
int n, m, q ;

pint base[N] ;

pint esab[N] ;

int ns[10][N] ;

pint line[10][2] ;

bitset <N> all ;
bitset <N> blw ;
bitset <N> below[10] ;

bool chk(pint a, pint b, pint c){
pint x = make_pair(b.fr - a.fr, b.sc - a.sc) ;
pint y = make_pair(c.fr - a.fr, c.sc - a.sc) ;
if (1ll * x.fr * y.sc - 1ll * y.fr * x.sc > 0) return 1 ; else return 0 ;
}
bool chk2(pint a, pint b, pint c){
pint x = make_pair(b.fr - a.fr, b.sc - a.sc) ;
pint y = make_pair(c.fr - a.fr, c.sc - a.sc) ;
if (1ll * x.fr * y.sc - 1ll * y.fr * x.sc < 0) return 1 ; else return 0 ;
}
bool comp1(pint a, pint b){
return a.fr == b.fr ? a.sc < b.sc : a.fr < b.fr ;
}
bool comp2(pint a, pint b){
return a.fr == b.fr ? a.sc > b.sc : a.fr < b.fr ;
}
int rev[N] ;
int main(){
cin >> n >> m >> q ;
for (int i = 1 ; i <= n ; ++ i) all[i] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
base[i].fr = qr(), base[i].sc = qr() ;
sort(base + 1, base + n + 1, comp1) ; int x, y ;
for (int i = 1 ; i <= n ; ++ i) esab[i] = base[i] ;
sort(esab + 1, esab + n + 1, comp2) ;
for (int i = 1 ; i <= n ; ++ i)
rev[i] = lower_bound(base + 1, base + n + 1, esab[i]) - base ;
// for (int i = 1 ; i <= n ; ++ i) cout << rev[i] << '\n' ;
for (int i = 1 ; i <= m ; ++ i){
line[i][0].fr = qr() ;
line[i][1].fr = qr() ;
line[i][0].sc = line[i][1].sc = qr() ;
}
blw.set() ; blw[0] = 0 ;
for (int i = 1 ; i <= m ; ++ i){
below[i].reset() ;
for (int j = 1 ; j <= n ; ++ j)
if (base[j].sc < line[i][0].sc)
below[i][j] = 1, ns[i][++ ns[i][0]] = j ;
}
while (q --){
x = qr(), y = qr() ;
pint now = make_pair(x, y) ;
bitset <N> ans, t, tt, tmp ;
ans.set() ; ans[0] = 0 ;
for (int i = 1 ; i <= m ; ++ i){
bool val1, val2 ;
int l = 1, r = n, mid, res = 0, old ;
if (x >= line[i][0].fr){
val1 = 0 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (chk(now, line[i][0], base[mid]))
res = mid, l = mid + 1 ; else r = mid - 1 ;
}
}
else {
val1 = 1 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (chk(now, line[i][0], esab[mid]))
res = mid, l = mid + 1 ; else r = mid - 1 ;
}
}
t = all & (all << (n - res)) ; t >>= n - res ;
for (int i = 1 ; i <= n + 10 ; ++ i) cout << t[i] << " " ; puts("") ;
cout << t.count() << '\n' ;
l = res + 1, r = n, old = res, res = n + 1 ;
if (x <= line[i][1].fr){
val2 = 0 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (chk2(now, line[i][1], esab[mid]))
res = mid, r = mid - 1 ; else l = mid + 1 ;
}
}
else {
val2 = 1 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (chk2(now, line[i][1], base[mid]))
res = mid, r = mid - 1 ; else l = mid + 1 ;
}
}
tt = (all >> res) << res ;
if (!val1){

}
if (val2){

}
for (int i = 1 ; i <= n + 10 ; ++ i) cout << t[i] << " " ; puts("") ;
cout << t.count() << '\n' ;
t |= below[i] ;
ans &= t ;
}
printf("%d\n", (int)ans.count()) ;
}
return 0 ;
}
「My-Code」
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
int ans ;
int n, m, q ;

vint s[36] ;

vdb Lr[36] ;
vdb Rr[36] ;

pint base[N] ;

pint line[10][2] ;

inline db getsec(const pint &x, const pint &y){
db d1 = x.fr - y.fr ;
db d2 = x.sc - y.sc ;
if (!d1) return x.fr ;
db k = (d2 / d1) ;
return (k * x.fr - x.sc) / k ;
}
inline int get_mask(int x){ return x ? -1 : 1 ; }
inline int do_do(const pint &d, int num, const vdb &L, const vdb &R){
db lc = -1e18, rc = 1e18 ;
for (auto k : s[num]){
chkmax(lc, getsec(d, line[k][0])) ;
chkmin(rc, getsec(d, line[k][1])) ;
}
// cout << lc << " " << rc << '\n' ;
int l = lower_bound(R.begin(), R.end(), rc) - R.begin() ;
int r = upper_bound(L.begin(), L.end(), lc) - L.begin() ;
// cout << num << " " << l << " " << r << '\n' ;
return max(0, (r - 1) - (l - 1)) ;
}
int main(){
cin >> n >> m >> q ; int x, y ;
for (int i = 1 ; i <= n ; ++ i)
base[i].fr = qr(), base[i].sc = qr() ;
for (int i = 1 ; i <= m ; ++ i){
line[i][0].fr = qr() ;
line[i][1].fr = qr() ;
line[i][0].sc = line[i][1].sc = qr() ;
}
for (int o = 1 ; o < (1 << m) ; ++ o){
for (int i = 1 ; i <= m ; ++ i)
if (1 << (i - 1) & o) s[o].p_b(i) ;
for (int i = 1 ; i <= n ; ++ i){
bool chk = 1 ;
for (auto k : s[o])
chk &= (line[k][0].sc < base[i].sc) ;
if (!chk) continue ;
db l = -1e18, r = 1e18 ;
for (auto k : s[o]){
chkmax(l, getsec(base[i], line[k][0])) ;
chkmin(r, getsec(base[i], line[k][1])) ;
}
// cout << o << " " << l << " " << r << '\n' ;
if (l <= r) Lr[o].p_b(l), Rr[o].p_b(r) ;
}
sort(Lr[o].begin(), Lr[o].end()) ;
sort(Rr[o].begin(), Rr[o].end()) ;
// cout << Lr[o].size() << " " << Rr[o].size() << '\n' ;
}
while (q --){
ans = n ;
x = qr(), y = qr() ;
pint now = make_pair(x, y) ;
for (int o = 1 ; o < (1 << m) ; ++ o)
ans += get_mask(s[o].size() & 1) * do_do(now, o, Lr[o], Rr[o]) ;
printf("%d\n", ans) ;
}
}

A.M.~P.M.

这个H1意思是上下午时间混着打的

A

大概就是暴力贪心。根据 $2^k>\sum _{j<k} 2^j$ 可以知道从最高位开始贪心一定没问题。秒了秒了。

「My-Code」
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
struct Edge{
int to, next ;
}E[MAXN << 1] ; int head[MAXN], cnt ; LL ans ;
int N, L[MAXN], R[MAXN], P[MAXN], A[MAXN], vis[MAXN] ;

void dfsp(int u){
if (!u) return ;
P[++ P[0]] = u ;
dfsp(L[u]), dfsp(R[u]) ;
}
void dfsa(int u){
if (!u) return ;
dfsa(L[u]), dfsa(R[u]) ;
A[++ A[0]] = u ;
}
LL expow(LL a, int b){
LL res = 1 ;
if (!a) return 0ll ;
while (b){
if (b & 1)
(res *= a) %= Mod ;
(a *= a) %= Mod, b >>= 1 ;
}
return res % Mod ;
}
int main(){
cin >> N ; int i, j, u, v ;
for (i = 1 ; i <= N ; ++ i)
scanf("%d%d", &u, &v), L[i] = u, R[i] = v ;
dfsp(1), dfsa(1) ; memset(vis, -1, sizeof(vis)) ;
for (i = 1, j = N - 1 ; i <= N ; ++ i, -- j){
if (vis[A[i]] > -1 && vis[P[i]] > -1)
(ans += expow(2 * vis[P[i]], j) - expow(2 * vis[A[i]], j) + Mod) %= Mod ;
else if (vis[P[i]] > -1) vis[A[i]] = 0, (ans += expow(2 * vis[P[i]], j)) %= Mod ;
else if (vis[A[i]] > -1) vis[P[i]] = 1, (ans += expow(2 * vis[P[i]], j) - expow(2 * vis[A[i]], j)) %= Mod ;
else vis[A[i]] = 0, vis[P[i]] = 1, (ans += expow(2 * vis[P[i]], j) - expow(2 * vis[A[i]], j)) %= Mod ;
}
cout << ((ans % Mod) + Mod) % Mod << endl ;
}

B

美团杯测试赛的 A。挺好一题,不再多说了。

C

咕咕咕咕咕。

P.M.

A

Sol 1 我的做法

考虑贪心着去做。首先不难发现子树之前独立,因为 Alice 肯定会选一棵最优的子树,如果 Alice 选择了某棵子树,她还需要再走回根的话显然不优。一开始想的直接拿每个点孩子中的叶子个数 $s(x)$ 和深度 $dep(x)$ 比一下,后来发现如果某个比较浅的地方有叶子的话,Bob 是一定要堵的,所以这部分Bob浪费的步数也要算上。

挂了一发后发现…原来 Bob 才是先手(smwy)。然后自己想的是一定会挑一个 $s(x)$ 尽量大且 $dep(x)$ 尽量小的叶子删掉。冷静了一会儿发现这并不是最优的策略。最优的策略应该是 Bob 预测到了 Alice 会怎么走并删除 Alice 路径上的某个关键叶子。于是就应该拿 $dep(x)$ 和 $s(x)-1$ 比较。

「My-Code」
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
int n, m ;
int dep[N] ;
int sum[N] ;
int leaf[N] ;

vint E[N] ;

void dfs(int x){
for (auto k : E[x]){
dep[k] = dep[x] + 1 ;
dfs(k) ; sum[x] += leaf[k] ;
}
if (!E[x].size()) leaf[x] = 1 ;
}
void dfs(int x, int k){
if (sum[x] + k > dep[x] + 1){
puts("Y") ; exit(0) ;
}
for (auto y : E[x])
if (!leaf[y]) dfs(y, k + sum[x]) ;
}
int main(){
cin >> n ; int x, y = 0 ;
for (int i = 2 ; i <= n ; ++ i)
x = qr(), E[x].p_b(i) ; dfs(1) ;
dfs(1, 0) ; return puts("D"), 0 ;
return 0 ;
}

Sol 2 std 的做法

说实话这种做博弈的思路我还是真没怎么见过。考虑直接 $dp$ 。设 $f_u$ 表示考虑了以 $u$ 为根的子树,Bob 要获胜的话需要提前操作多少次。那么会有转移

因为 Bob 至少要把所有叶子都删掉,且可以提前操作一次。最后如果 $f_1=0$ 那么Bob 必胜。

B

谔谔题。考虑随便选 $k$ 个点组成的凸包点编号可能不连续,所以正着做很难,于是考虑反着做,维护被删掉的面积。具体的,可以用三角剖分求出任意一段连续编号 $[i,j]$ 之间的多边形面积 ${\rm S}_{i,j}$ 。然后删掉它的多边形方案数就是 $\binom{n-(j-i+1)}{k-2}$ 。然后加一遍就好了。

不过我认为这题的亮点在于卡常。这题由于涉及到 $5e3$ 级别的的组合数,精度很难保证。全开 long double 时间会很爆炸 。于是考虑这么几条卡常攻略:

1、$\binom{n}{k-2}$ 可以线性暴力算。

2、用 $\binom{n}{k}=\binom{n-1}{k}\cdot \frac{n}{n-k}$ 来算出所有的 $\binom{n-(j-i+1)}{k-2}$ 。

3、除法和三角剖分乘 $0.5$ 什么的可以最后一起算。

然后大概就能快个三倍左右。

「My-Code」
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

const int N = 5010 ;

int n, m ;
struct Node{
ldb x ;
ldb y ;
}base[N] ;

ldb ans ;
ldb sum ;
//ldb fac[N] ;
//ldb inv[N] ;
ldb pks[N] ;
db f[N][N] ;
//db comb[N][N] ;

//ldb binom(int x, int y){ return fac[x] / fac[y] / fac[x - y] ; }
inline db operator * (const Node &a, const Node &b){ return (a.x * b.y - a.y * b.x) ; }

int main(){
cin >> n >> m ;
pks[m - 2] = 1.0 ; sum = 1.0 ;
for (int i = m - 1 ; i <= n ; ++ i)
pks[i] = pks[i - 1] * (ldb)i / (ldb)(i - m + 2) ;
for (int i = 1 ; i <= m ; ++ i)
sum = sum / (ldb)i * (ldb)(n - i + 1) ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%Lf%Lf", &base[i].x, &base[i].y) ;
for (int i = 1 ; i <= n ; ++ i) base[i + n] = base[i] ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= i + n - 1 ; ++ j)
f[i][j] = f[i][j - 1] + base[j - 1] * base[j] ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= i + n - 1 ; ++ j)
f[i][j] = fabs(f[i][j] + base[j] * base[i]) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n - m + i + 1 ; ++ j)
ans += f[i][j] * pks[n - (j - i + 1)] ;
ans = f[1][n] - ans / sum ;
printf("%.10Lf", 0.5 * ans) ; return 0 ;
}

C

这题是真的有趣。

$1\leq n\leq 2\times10^5$ 。

orz 又是找性质…又是找性质…怎么又是找性质Qaq

考虑 $35$ 分暴力怎么做。设 $f_i$ 表示前 $i$ 根弦都被删除的最小代价。考虑转移。考虑怎样的转移会合法,那必然是 $j$ 和 $i$ 把 $[i,j]$ 之间所有弦都给删掉才算合法。那么不难决策点 $j_1,j_2,j_3\cdots j_k$ 一定满足这种性质:

首先不难知道,如果一条弦会被 $i$ 割掉,那么拿他转移一定不会优。因此只有当一条比较远的弦可以把比较近的所有决策点都割掉,前 $i$ 条弦才都可以被割掉。那么就可以 $O(n^2)$ dp了。

同时注意到有一档部分分是说 $|i-p_i|\leq 5$ 。据此可以知道决策点数量一定不会太多。于是这部分就比较玄学,可以只扫 $|i-j|<20$ 的所有 $j$ 来转移。

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
//55pts
int n ;
int f[N] ;
int rev[N] ;
int pos[N] ;
int base[N] ;

int main(){
cin >> n ;
memset(f, 127, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i)
rev[pos[i] = qr()] = i ; f[0] = 0 ;
rev[n + 1] = pos[n + 1] = n + 1 ;
for (int i = 1 ; i <= n ; ++ i) base[i] = qr() ;
for (int i = 1 ; i <= n + 1 ; ++ i){
for (int j = i - 1, mx = 0 ; j >= 0 ; -- j){
if (n >= 3000 && i - j >= 16) break ;
if (pos[j] >= mx && pos[j] < pos[i])
mx = pos[j], chkmin(f[i], base[i] + f[j]) ;
}
// for (int j = pos[i] - 1, k = 0 ; j >= 0 ; -- j)
// if (rev[j] >= k && rev[j] < i)
// chkmax(k, rev[j]), chkmin(f[i], base[i] + f[rev[j]]) ;
}
cout << f[n + 1] << '\n' ; return 0 ;
}

以下是错误的瞎 bb。

然后这个 $100$ 分就十分的强。首先来考虑,这些决策点之间并不连续,很难用数据结构维护。但是我们可以观察对于每个 $i$ 的决策点的数量和。考虑这个值一定有一个下界,这个下界本质上就是

$\{p_n\}$ 是一个 $1\sim n$ 的排列。求

其中 $(l,r)$ 表示一段连续的值域。

直观的感受是,似乎不是很大?因为如果 $\sqrt n$ 分块去卡的话也只会卡到 $n$ 左右。仔细观察的话可以发现——每个 $j$ 只会产生至多 $1$ 的贡献。原因是每个 $j$ 的贡献都只会被算到后面的第一个 $i$ 上。

所以可以每次询问暴力所有的决策点,在一个线段树上用 $\max\{p_i\}$ 二分一下就好了。复杂度 $O(n\log ^2 n)$ 。

为什么错呢?因为这!根!本!就!不!是!他!的!上!界!。注意到 max 取得不是所有 j+1~i 而是合法的 j+1~i。所以这个上界根本不对。那么问题大概就是这样的:

大概就是许多人这题复杂度写的是不对的…写法大概是线段树上只维护 p[i] 的区间最大值,询问的时候根据这个在线段树上二分。但这个二分是假的,复杂度是 $O(\sum (\zeta(i))\cdot \rm poly\log)$,其中 $\zeta(i)$ 是 $i$ 的决策点个数。那也就是说大概是如下程序的 $cnt$ 值乘上一个 $\rm polylog$:

1
2
3
4
for (int i = 1 ; i <= n + 1 ; ++ i)
for (int j = i - 1, mx = 0 ; j >= 0 ; -- j)
if (pos[j] >= mx && pos[j] < pos[i])
mx = pos[j], ++ cnt ;

然后这个复杂度是显然不对的。考虑将题目中的 $\{p_n\}$ 按照这种方式生成:

1
n/2,n/2-1,n/2-2 … 1,n,n-1,n-2 … n/2+1

那么就可以轻易被卡到 $n^2$ 。

链接:https://pan.baidu.com/s/1WeQD6qsORfyUmX6LeONuRw 密码:ua1f

由于不会写 Validator 所以大家可以自行测一下自己的程序

不过在不特别卡的情况下,这个 $cnt$ 会是 $O(n\ln n)$ 的级别。据 mls 说是跟单调栈在每个位置的期望长度之和是一个界。这也是为什么这些错解能过掉的原因。

= = 这就很狗。

所以正确的写法应该是合并的时候将 $dp$ 值一起合并进去。这样 update 的时候就是 $\log ^2$ 的了。最后总复杂度 $O(n\log ^2n)$ 。

仔细分析一下细节,其实本质上跟「兔队线段树」里面讲的内容差不多。考虑维护这样两个值:该节点的总贡献,和考虑了该节点右子树后该节点左子树的贡献。那么由于每个右子树都会对左子树产生不同程度的影响,所以我们本质上只关心第二个值,第一个值只会起辅助作用。然后是每个函数的细节:

0、考虑对着 $p_i$ 建立线段树,每个点维护键值 $i$ 和权值 $dp_i$ 。

1、query 。大概就是考虑必然是要先进右子树再进左子树。最后会返回一个 calc(root,l,r,limx) 的函数。

2、update。只需要考虑在 push_up 的时候,先计算在右子树影响下左子树的贡献,然后和右子树的贡献合并就好了。

3、考虑 calc 函数本质上是在计算在 limx 这个限制的影响下以 root 为根的子树的贡献。注意到由于维护了一个「考虑了该节点右子树的影响后该节点左子树的贡献」,可以知道如果当前的最大的 $j$ 满足 $j\gt \max_{j’\in rchild} j’$,那么就只需要关心右子树中的贡献,就可以递归进右子树并类加上 $lchild$ 的贡献;否则进入左子树。

感觉比较精妙的地方就在于维护了一个「考虑了该节点右子树的影响后该节点左子树的贡献」,这样就可以直接在线段树上进行复杂度正确的二分了。

「复杂度不对的代码」
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

int n ;
int f[N] ;
int rev[N] ;
int pos[N] ;
int base[N] ;

int f_now ;
int now_mx ;
int val[N * 3] ;
int seg[N * 3] ;

#define lc (rt << 1)
#define rc (rt << 1 | 1)

int calc(int rt, int l, int r){
if (seg[rt] < now_mx) return Inf ;
if (l == r) return now_mx = seg[rt], val[rt] ;
int mid = (l + r) >> 1 ; int ret = Inf ;
if (seg[rc] > now_mx) ret = calc(rc, mid + 1, r) ;
if (seg[lc] > now_mx) chkmin(ret, calc(lc, l, mid)) ;
return ret ;
}
int qry(int rt, int l, int r, int limx){
if (r <= limx)
return calc(rt, l, r) ;
int mid = (l + r) >> 1, ret = Inf ;
if (limx > mid) ret = qry(rc, mid + 1, r, limx) ;
chkmin(ret, qry(lc, l, mid, limx)) ;
return ret ;
}
void upd(int rt, int l, int r, int po, int v1, int v2){
if (l == r)
return seg[rt] = v1, void(val[rt] = v2) ;
int mid = (l + r) >> 1 ;
if (po <= mid) upd(lc, l, mid, po, v1, v2) ;
else upd(rc, mid + 1, r, po, v1, v2) ;
seg[rt] = max(seg[lc], seg[rc]) ;
}
int main(){
cin >> n ;
memset(f, 127, sizeof(f)) ;
if (n <= 2000){
for (int i = 1 ; i <= n ; ++ i)
rev[pos[i] = qr()] = i ; f[0] = 0 ;
rev[n + 1] = pos[n + 1] = n + 1 ;
for (int i = 1 ; i <= n ; ++ i) base[i] = qr() ;
for (int i = 1 ; i <= n + 1 ; ++ i){
for (int j = i - 1, mx = 0 ; j >= 0 ; -- j){
if (n >= 3000 && i - j >= 16) break ;
if (pos[j] >= mx && pos[j] < pos[i])
mx = pos[j], chkmin(f[i], base[i] + f[j]) ;
}
// for (int j = pos[i] - 1, k = 0 ; j >= 0 ; -- j)
// if (rev[j] >= k && rev[j] < i)
// chkmax(k, rev[j]), chkmin(f[i], base[i] + f[rev[j]]) ;
}
cout << f[n + 1] << '\n' ; return 0 ;
}
else {
pos[n + 1] = n + 1 ;
memset(val, 127, sizeof(val)) ;
for (int i = 1 ; i <= n ; ++ i) pos[i] = qr() ;
for (int i = 1 ; i <= n ; ++ i) base[i] = qr() ;
for (int i = 1 ; i <= n + 1 ; ++ i){
f_now = qry(1, 1, n + 1, pos[i]) ;
// cout << i << " " << f_now << '\n' ;
f[i] = base[i] + (f_now >= Inf ? 0 : f_now) ;
upd(1, 1, n + 1, pos[i], i, f[i]), now_mx = 0 ;
// cout << f[i] << '\n' ;
}
cout << f[n + 1] << '\n' ;
}
return 0 ;
}
「复杂度正确的代码」
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
#define ycy make_pair

int n ;
int f[N] ;
int rev[N] ;
int pos[N] ;
int base[N] ;

pint f_now ;
pint ept_val ;
pint zero_val ;

#define lc (rt << 1)
#define rc (rt << 1 | 1)

pint val[N * 3] ;
pint lval[N * 3] ;

il int mx(int x, int y){ return x > y ? x : y ; }
il int mn(int x, int y){ return x < y ? x : y ; }

il pint merge(const pint &x, const pint &y){
return ycy( mx(x.fr, y.fr), mn(x.sc, y.sc) ) ;
}
il pint solve(int rt, int l, int r, const pint & now){
// cout << l << " " << r << ' ' << now.fr << ' ' << now.sc << '\n' ;
if (val[rt].fr <= now.fr) return ept_val ;
if (l == r) return val[rt] ;
int mid = (l + r) >> 1 ;
if (now.fr < val[rc].fr)
return merge(lval[rt], solve(rc, mid + 1, r, now)) ;
else return solve(lc, l, mid, now) ;
}
void push_up(int rt, int l, int r){
int mid = (l + r) >> 1 ;
lval[rt] = solve(lc, l, mid, val[rc]) ;
val[rt] = merge(lval[rt], val[rc]) ;
}
void upd(int rt, int l, int r, int po, const pint &v){
if (l == r)
return void(val[rt] = v) ;
int mid = (l + r) >> 1 ;
if (po <= mid) upd(lc, l, mid, po, v) ;
else upd(rc, mid + 1, r, po, v) ;
push_up(rt, l, r) ;
}
void qry(int rt, int l, int r, int po){
// cout << l << " " << r << '\n' ;
if (r <= po)
return void(f_now = merge(f_now, solve(rt, l, r, f_now))) ;
int mid = (l + r) >> 1 ;
if (mid < po) qry(rc, mid + 1, r, po) ;
qry(lc, l, mid, po) ;
}

int main(){
cin >> n ;
pos[n + 1] = n + 1 ;
ept_val = ycy(-1, Inf) ;
zero_val = ycy(2333, 0) ;
for (int i = 1 ; i <= n ; ++ i) pos[i] = qr() ;
for (int i = 1 ; i <= n ; ++ i) base[i] = qr() ;
for (int i = 1 ; i <= n * 3 ; ++ i)
val[i] = ept_val, lval[i] = ept_val ;
for (int i = 1 ; i <= n + 1 ; ++ i){
// cout << i << '\n' ;
f_now = ept_val ;
// cout << i << '\n' ;
qry(1, 1, n, pos[i]) ;
// cout << i << '\n' ;
if (f_now == ept_val)
f_now = zero_val ;
// cout << i << '\n' ;
f[i] = base[i] + f_now.sc ;
upd(1, 1, n, pos[i], ycy(i, f[i])) ;
}
// debug(f, 1, n + 1) ;
cout << f[n + 1] << " " ;
return 0 ;
}

有有有点吓人。理论复杂度正确的代码居然比不正确的慢 $1000ms+$ 。