Loj 2773 学习轨迹

Posted on | Edited on | Views:

单调栈 + 线段树.

首先,若在学校 $A$ 选的课权值和不超过 $A$ 权值总和一半,且在学校 $B$ 选的课权值和也不超过 $B$ 权值一半,显然是不如将 $A$ 的课选完或将 $B$ 的课选完其中之一优的,所以至少要有一所学校选的课权值和超过它权值总和的一半.

先假定在学校 $A$ 选的课权值必须超过其总权值一半,算完后交换两个学校再做一次.

记 $p$ 为 $A$ 中第一个权值前缀和超过总权值一半的位置,则在 $A$ 选的区间必定包含 $p$ ,否则肯定不能超过总权值一半.

此时在学校 $B$ 中选择一个区间 $[l,r]$ ,区间内的点会 ban 掉学校 $A$ 中的一些点,此时在学校 $A$ 的选择方法就是从 $p$ 向两边延伸,直到遇到被 ban 掉的点,中间的点权值和就是在 $A$ 中的最大收益.

枚举 $B$ 中选择的区间右端点 $r$ ,用线段树维护选择每个 $l$ 对应的区间 $[l,r]$ 时 $p$ 能拓展到的最远左右端点.

$r$ 增大 $1$ 时, 每个 $[l,r]$ 会新增同一个被 ban 掉的点,若这个被 ban 掉的点已在 $p$ 能拓展到的区间之外,就不用考虑,于是对 $p$ 的左右端点各维护一个单调栈,每次新增 ban 掉的点时,不断将它能覆盖的点弹出,在线段树上做修改即可.

时间复杂度 $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
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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define y1 ysgh
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-') 
		jp = getchar();
	if (jp == '-') fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9') 
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10) print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0) putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 5e5 + 10;
int n, m, a[N], b[N], c[N << 1], p1, p2, p3, p4, swaped = 0;
ll ans, suma[N], sumb[N];
ll mx[N << 2], ext[N << 2];
void pushup(int x)
{
	mx[x] = max(mx[x << 1], mx[x << 1 | 1]) + ext[x];
}
void BuildTree(int x, int l, int r)
{
	ext[x] = 0;
	if (l == r)
	{
		mx[x] = suma[n] - sumb[l - 1];
		return;
	}
	int mid = (l + r) >> 1;
	BuildTree(x << 1, l, mid);
	BuildTree(x << 1 | 1, mid + 1, r);
	pushup(x);
}
void upd(int x, int l, int r, int L, int R, ll d)
{
	if (L <= l && r <= R)
	{
		mx[x] += d, ext[x] += d;
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
		upd(x << 1, l, mid, L, R, d);
	if (R > mid)
		upd(x << 1 | 1, mid + 1, r, L, R, d);
	pushup(x);
}
int query(int x, int l, int r)
{
	if (l == r)
		return l;
	int mid = (l + r) >> 1;
	if (mx[x] == mx[x << 1] + ext[x])
		return query(x << 1, l, mid);
	return query(x << 1 | 1, mid + 1, r);
}
void report(ll val, int a, int b, int c, int d)
{
	if (val > ans)
	{
		if (swaped)
			swap(a, c), swap(b, d);
		ans = val, p1 = a, p2 = b, p3 = c, p4 = d;
	}
}
int tpl, tpr, sl[N], sr[N];
void solve()
{
	int p = lower_bound(suma + 1, suma + n + 1, (suma[n] + 1) >> 1) - suma;
	BuildTree(1, 1, m);
	tpl = tpr = 0;
	for (int i = 1; i <= m; ++i)
	{
		if (b[i])
		{
			if (b[i] <= p)
			{
				while (tpl && b[i] > b[sl[tpl]])
				{
					upd(1, 1, m, sl[tpl - 1] + 1, sl[tpl], suma[b[sl[tpl]]]);
					--tpl;
				}
				upd(1, 1, m, sl[tpl] + 1, i, -suma[b[i]]);
				sl[++tpl] = i;
			}
			else
			{
				while (tpr && b[i] < b[sr[tpr]])
				{
					upd(1, 1, m, sr[tpr - 1] + 1, sr[tpr], suma[n] - suma[b[sr[tpr]] - 1]);
					--tpr;
				}
				upd(1, 1, m, sr[tpr] + 1, i, suma[b[i] - 1] - suma[n]);
				sr[++tpr] = i;
			}
		}
		int j = query(1, 1, m);
		int pl = lower_bound(sl + 1, sl + tpl + 1, j) - sl;
		int pr = lower_bound(sr + 1, sr + tpr + 1, j) - sr;
		pl = pl <= tpl ? b[sl[pl]] + 1 : 1;
		pr = pr <= tpr ? b[sr[pr]] - 1 : n;
		report(sumb[i] + mx[1], pl, pr, j, i);
	}
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = 1; i <= n; ++i) suma[i] = suma[i - 1] + read();
	for (int i = 1; i <= m; ++i) c[read()] = i;
	for (int i = 1; i <= m; ++i) sumb[i] = sumb[i - 1] + read();
	for (int i = 1; i <= n; ++i) a[i] = c[a[i]], b[a[i]] = i;
	report(suma[n], 1, n, 0, 0), report(sumb[m], 0, 0, 1, m);
	solve();
	swap(n, m), swap(a, b), swap(suma, sumb), swaped = 1;
	solve();
	printf("%lld\n", ans);
	printf("%d %d\n", p1, p2);
	printf("%d %d\n", p3, p4);
	return 0;
}