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;
}