10.10 携程笔试

前两题都比较简单，这里给出后两题我的解法

3. 给一个长为n的数组a，将其分成恰好m个非空子数组，对每个子数组内部求gcd，求m个gcd值的和的最大值，1≤m≤n≤400。

   典型的区间dp问题。

   首先计算gcd[l][r]表示数组下标l到r的gcd值，后续考虑dp[i+1][j+1]表示到第i个数字，恰好分成j个子数组的gcd的和的最大值。初始dp[0][0]=0，其余为-inf。转移时遍历当前子数组的左端点[0,i]，即:

   

   时间复杂度

4. 给一个长为n的数组a，有q次查询，每次查询为[op, l, r]，若op=1则计算 a[l] & a[l+1] | a[l+2] & a[l+3] | a[l+4] ... a[r], 否则计算 a[l] | a[l+1] & a[l+2] | a[l+3] & a[l+4] ... a[r]。1≤n,q≤1e5

   这里我给出我的解法，比较复杂，不知道有没有更好的方法。

   首先观察两种查询，可以发现第二种查询可以转换成第一种查询，这是因为

   

   将 修改成 即可，查询后再修改回来。因此只需要处理第一种查询即可。

   涉及到区间查询和单点修改，考虑使用线段树。代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int M = (1 << 30) - 1;

struct node {
    int v1 = 0, v2 = M;
    int v3 = 0, v4 = M;
};

node merge(node& a, node& b) {
    node res;
    res.v1 = (a.v1 & b.v2) | b.v1;
    res.v2 = a.v2 & b.v2;
    res.v3 = (a.v3 & b.v4) | b.v3;
    res.v4 = a.v4 & b.v4;
    return res;
}

struct segtree {
    vector<node> tr;
    int n;

    void build(vector<int>& a, int p, int l, int r) {
        if (l == r) {
            if (l & 1) tr[p].v1 = tr[p].v4 = a[l];
            else tr[p].v3 = tr[p].v2 = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, p<<1, l, mid);
        build(a, p<<1|1, mid+1, r);
        tr[p] = merge(tr[p<<1], tr[p<<1|1]);
    }

    segtree(vector<int> &a) : n(a.size()) {
        tr.resize(n * 4 + 5);
        build(a, 1, 0, n-1);
    }

    node query(int p, int l, int r, int s, int t) {
        if (s > r || t < l) return node{};
        if (s <= l && t >= r) return tr[p];
        int mid = (l + r) / 2;
        node p1, p2;
        if (mid >= s) p1 = query(p<<1, l, mid, s, t);
        if (mid < t) p2 = query(p<<1|1, mid+1, r, s, t);
        return merge(p1, p2);
    }

    void update(int p, int l, int r, int x, int v) {
        if (l == r) {
            if (l & 1) tr[p].v1 = tr[p].v4 = v;
            else tr[p].v3 = tr[p].v2 = v;
            return;
        }
        int mid = (l + r) / 2;
        if (mid >= x) update(p<<1, l, mid, x, v);
        else update(p<<1|1, mid+1, r, x, v);
        tr[p] = merge(tr[p<<1], tr[p<<1|1]);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    segtree tree(a);
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            node res = tree.query(1, 0, n, l, r);
            if (l & 1) cout << res.v1 << '\n';
            else cout << res.v3 << '\n';
        } else {
            tree.update(1, 0, n, l-1, M);
            node res = tree.query(1, 0, n, l-1, r);
            if (l-1 & 1) cout << res.v1 << '\n';
            else cout << res.v3 << '\n';
            tree.update(1, 0, n, l-1, a[l-1]);
        }
    }
}