20231029题解


perm

\(S = \frac{x + y}{\operatorname{gcd}(x, y)}\),打表出结论:

\[ f(x, y)= \begin{cases} \log_2 S &\log_2 S \in \mathbb{Z} \\ 0 & \text{otherwise.} \end{cases} \]

所以我们可以枚举 \(\operatorname{gcd}(x, y),x,S\),对于每一个 \(x\) 寻找有哪些 \(y\) 使得 \(f(x, y) \ne 0\),我们把这些数记为一个序列 \(p_i\)。时间复杂度 \(\mathcal{O}(n\log^2{n})\)

接下来考虑原题:记 \(S(l, r)=\sum_{i=1}^{l}\sum_{j=1,j \ne i}^{r}f(i,j)\),则要求的结果就是 \(\frac{1}{2}(S(r, r)-S(r, l-1)-S(l-1, r)+S(l-1, l-1))\)。离线这些 \(S\)。这是一个类似于二维偏序的问题:维护一个树状数组,从小到大枚举 \(i\),将树状数组的 \(p_{ij}\) 位置加上 \(f(a_i, a_{p_{ij}})\)。这样,当 \(i\) 枚举完时,\(S(i, r)=\operatorname{query}(r),\operatorname{query}\) 是树状数组查询函数。\(i\) 从 1 枚举到 \(n\),所有的 \(S\) 也自然被解决。

总时间复杂度大概 \(\mathcal{O}(q \log n + n \log^3 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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5, maxq = 1e6 + 5;
int n, a[maxn], q, b[maxn], ans[maxq], c[maxn];
vector<int> p[maxn];
struct node { int id, from; node() {} node(int id, int from): id(id), from(from) {}};
vector<node> qq[maxn];
void update(int pos, int x) {...}
int ask(int pos) {...}

int main() {
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
read(n);
for (int i = 1; i <= n; i++) read(a[i]), b[a[i]] = i;
for (int d = 1; d <= n; d++) {
for (int i = d; i <= n; i += d) {
for (int j = 2; j * d - i <= n; j <<= 1) {
if (j * d <= i) continue;
if (__gcd(i, j * d - i) != d) continue;
if (j * d == i * 2) continue;
p[b[i]].emplace_back(b[j * d - i]);
}
}
}
read(q);
for (int i = 1; i <= q; i++) {
int l, r; read(l); read(r);
qq[l - 1].emplace_back(l - 1, i);
qq[l - 1].emplace_back(r, -i);
qq[r].emplace_back(l - 1, -i);
qq[r].emplace_back(r, i);
}
for (int i = 1; i <= n; i++) {
for (int j : p[i]) update(j, __builtin_ctz((a[i] + a[j]) / __gcd(a[i], a[j])));
for (auto x : qq[i]) {
if (x.from > 0) ans[x.from] += ask(x.id);
else ans[-x.from] -= ask(x.id);
}
}
for (int i = 1; i <= q; i++) printf("%d\n", ans[i] / 2);
return 0;
}

lis

出题人出来谢罪:反转的意思是文艺平衡树那种区间翻转,而不是 01 取反。

考虑如何快速求一个 01 串的 LIS:如果 1 的个数是 \(cnt_1\),那么我们新构造一个序列,原串中的 1 变成 -1,0 变成 1,然后求新序列的最大前缀和 \(S\),则 LIS 长度就是 \(cnt_1 + S\)

(其实就是看从哪里开始把取 0 变成取 1)

这样就变成了最大前缀和的问题。

又由于题目说可以翻转,原来连续的一段前缀,在翻转 \(k\) 次后,一定可以变成一段前缀 +\(k\) 段不相交的子段。子段内部翻不翻转其实对总和没影响。所以我们只要求原序列的最大 \(k\) 子段和。

这个东西可以 \(\mathcal{O}(nm)\) DP,有 70 pts。不过我们可以采取可反悔贪心的方法:找到当前的最大子段和,把和加入答案,之后对于子段内元素全部变成相反数。这样下次如果另一个子段取到了相交的部分,相交部分就相当于没取。

另外细节上来说,可以只翻转 1 个元素,相当于没做。所以如果有一次所有元素都是负的,没必要继续统计答案了,答案已经是最大值。

剩下就是怎么维护最大子段和。我们要知道具体是哪一个子段,还要支持区间取相反数。

这个东西可以用线段树做。口述太麻烦了,我先把结构体定义的代码放一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct val_t { 
int lmaxr, rmaxl, mmaxl, mmaxr, lminr, rminl, mminl, mminr;
/*
lmaxr:以左端点为开头的最大子段和的右端点
rmaxl:以右端点为开头的最大子段和的左端点
mmaxl, mmaxr:区间内最大子段和的左、右端点
lminr, rminl, mminl, mminr:同理,只不过是最小子段和
*/
long long sum, lmaxs, rmaxs, mmaxs, lmins, rmins, mmins;
/*
sum:区间和
lmaxs:以左端点为开头的最大子段和
rmaxs:以右端点为开头的最大子段和
mmaxs:区间内最大子段和
lmins, rmins, mmins:同理,只不过是最小子段和
*/
val_t() {} val_t(long long v, int id) { //单点赋值
lmaxr = rmaxl = mmaxl = mmaxr = lminr = rminl = mminl = mminr = id;
sum = lmaxs = rmaxs = mmaxs = lmins = rmins = mmins = v;
}
};

然后是合并:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
val_t operator & (const val_t &a, const val_t &b) {
val_t res; res.sum = a.sum + b.sum;

//处理左端点开始的子段和:a的左端子段和 / a区间和+b左端子段和
if (a.sum + b.lmaxs > a.lmaxs) res.lmaxr = b.lmaxr, res.lmaxs = a.sum + b.lmaxs;
else res.lmaxr = a.lmaxr, res.lmaxs = a.lmaxs;
if (a.sum + b.lmins < a.lmins) res.lminr = b.lminr, res.lmins = a.sum + b.lmins;
else res.lminr = a.lminr, res.lmins = a.lmins;

//处理右端点开始的子段和:b的右端子段和 / b区间和+a右端子段和
if (b.sum + a.rmaxs > b.rmaxs) res.rmaxl = a.rmaxl, res.rmaxs = b.sum + a.rmaxs;
else res.rmaxl = b.rmaxl, res.rmaxs = b.rmaxs;
if (b.sum + a.rmins < b.rmins) res.rminl = a.rminl, res.rmins = b.sum + a.rmins;
else res.rminl = b.rminl, res.rmins = b.rmins;

//处理子段和:a子段和 / b子段和 / a右端+b左端
res.mmaxs = a.rmaxs + b.lmaxs, res.mmaxl = a.rmaxl, res.mmaxr = b.lmaxr;
res.mmins = a.rmins + b.lmins, res.mminl = a.rminl, res.mminr = b.lminr;
if (a.mmaxs > res.mmaxs) res.mmaxs = a.mmaxs, res.mmaxl = a.mmaxl, res.mmaxr = a.mmaxr;
if (b.mmaxs > res.mmaxs) res.mmaxs = b.mmaxs, res.mmaxl = b.mmaxl, res.mmaxr = b.mmaxr;
if (a.mmins < res.mmins) res.mmins = a.mmins, res.mminl = a.mminl, res.mminr = a.mminr;
if (b.mmins < res.mmins) res.mmins = b.mmins, res.mminl = b.mminl, res.mminr = b.mminr;
return res;
}

还有取相反数:

1
2
3
4
5
6
7
8
9
val_t operator ~(const val_t &x) {
val_t res; res.sum = -x.sum;
//注意负号不要少:取相反数后,先同时取负号,然后最大变最小
res.lmaxr = x.lminr, res.lmaxs = -x.lmins, res.lminr = x.lmaxr, res.lmins = -x.lmaxs;
res.rmaxl = x.rminl, res.rmaxs = -x.rmins, res.rminl = x.rmaxl, res.rmins = -x.rmaxs;
res.mmaxl = x.mminl, res.mmaxr = x.mminr, res.mmaxs = -x.mmins;
res.mminl = x.mmaxl, res.mminr = x.mmaxr, res.mmins = -x.mmaxs;
return res;
}

完整代码:

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
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {...}

const int maxn = 2e5 + 5;
int n, m;
long long a[maxn], ans;

struct val_t {...};
val_t operator & (const val_t &a, const val_t &b) {...}
val_t operator ~(const val_t &x) {...}
struct node; typedef node* pos;
struct node { int l, r; val_t val; bool tag; pos ls, rs; node() {ls = rs = this;}}
buf[maxn << 1], *buf_pos = buf, *root = buf;
void push_up(pos p) { p -> val = p -> ls -> val & p -> rs -> val; }
void update_one(pos p) { p -> val = ~p -> val; p -> tag ^= 1; }
void push_down(pos p) { if (p -> tag) update_one(p -> ls), update_one(p -> rs), p -> tag = false; }
pos new_node(int l, int r) { pos p = ++buf_pos; p -> l = l, p -> r = r, p -> ls = p -> rs = buf; return p; }
void build(pos p) {
if (p -> l == p -> r) p -> val = val_t(a[p -> l], p -> l);
else {
int mid = (p -> l + p -> r) >> 1;
p -> ls = new_node(p -> l, mid), build(p -> ls);
p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
push_up(p);
}
}
void update(pos p, int l, int r) {
if (l > p -> r || r < p -> l) return;
if (l <= p -> l && p -> r <= r) return update_one(p);
push_down(p), update(p -> ls, l, r), update(p -> rs, l, r), push_up(p);
}
val_t ask(pos p, int l, int r) {
if (l <= p -> l && p -> r <= r) return p -> val;
push_down(p);
if (l <= p -> ls -> r && r >= p -> rs -> l) return ask(p -> ls, l, r) & ask(p -> rs, l, r);
else if (l <= p -> ls -> r) return ask(p -> ls, l, r);
else return ask(p -> rs, l, r);
}

int main() {
freopen("lis.in", "r", stdin);
freopen("lis.out", "w", stdout);
read(n);
for (int i = 1; i <= n; i++) {
int x, y; read(x); read(y);
a[i] = (x ? -y : y);
ans += (x ? y : 0);
}
read(m);
root = new_node(1, n); build(root);
long long s = 0, tmp = 0; int id = 0;
for (int i = 1; i <= n; i++) {
s += a[i]; if (s > tmp) id = i, tmp = s;
}
if (id) ans += tmp, update(root, 1, id);
printf("%lld\n", ans);
for (int j = 1; j <= m; j++) {
auto x = ask(root, 1, n);
if (x.mmaxs > 0) {
ans += x.mmaxs;
update(root, x.mmaxl, x.mmaxr);
}
printf("%lld\n", ans);
}
return 0;
}