Codeforces Round #1074(Div.4)

D脑子抽了WA了五发，H不是我能做出来的，赛时出A-G差不多了，反正是Unr。

D

题目大意：给定 $a_1,a_2,\ldots,a_n$ ，进行 $m$ 次操作，每次 $a_{b_i}+=c_i$ ，当任意元素大于 $h$ 时，所有元素重置回初始值，请求出最后的结果数。

数据范围： $1 \leq n,m \leq 2 \cdot 10^5,1 \leq h \leq 10^9$ ，其中 $n,m$ 的和不超过 $2 \cdot 10^5$ 。

思路：一开始想的就是模拟，但是没想到d4D就能上强度，直接吃了一发TLE，随后脑子有点蠢，一直想着二分最后一次重置或者倒序遍历，但是注意到重置只和顺序遍历有关，倒序或者二分会丢失这一信息，因此还是顺序遍历。

于是，顺序遍历怎么优化呢？由于每个数组的变化是稀疏的，因此完全可以用一个数组存储上次重置到这次的所有变化而不更新原数组，每次检测到重置则直接清空数组，最终用存储的变化更新原来数组就是最终结果，时间复杂度为 $O(N+M)$ 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void solve() {
    int n, m, h;
    cin >> n >> m >> h;
    vector<int> a(n);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    vector<int> b(m);
    vector<int> c(m);
    vector<int> diff(n);
    vector<int> re;
    for (int i = 0; i <= m - 1; i++) {
        cin >> b[i] >> c[i];
        diff[b[i] - 1] += c[i];
        re.push_back(i);
        if (diff[b[i] - 1] + a[b[i] - 1] > h) {
            for (int p : re) {
                diff[b[p] - 1] = 0;
            }
            re.clear();
        }
    }
    for (int i = 0; i <= n - 1; i++) cout << a[i] + diff[i] << ' ';
    cout << endl;
    return;
}

E

题目大意：在一条数轴上有 $n$ 个机器人和 $m$ 个障碍物，机器人走到障碍物上就会死。现在给定长度为 $k$ 的字符串，其为L则代表机器人全部往左走一步，反之全部往右走一步，问对于所有的 $i (1 \leq i \leq k)$ ，给出第 $i$ 步后活着的机器人数量。

数据范围： $1 \leq n,m,k \leq 2 \cdot 10^5$ ，它们的和不超过 $2 \cdot 10^5$

思路：注意到机器人如果死，必然是走到左右的障碍物死的，因此可以预处理轨迹的时间点，再预处理左右的距离，得到每个时间点死去的机器人数量，最后使用差分即可。

 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


void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    vector<int> b(m);
    for (int i = 0; i <= n - 1; i++) cin >> a[i];
    for (int i = 0; i <= m - 1; i++) cin >> b[i];
    ranges::sort(b);
    string s;
    cin >> s;
    vector<int> mo(k + 1);
    vector<int> l(n, INT_MIN);
    vector<int> r(n, INT_MAX);
    vector<int> die(k + 1, 0);
    map<int, int> ma;
    for (int i = 1; i <= k; i++) {
        if (s[i - 1] == 'L')
            mo[i] = mo[i - 1] - 1;
        else
            mo[i] = mo[i - 1] + 1;
        if (!ma.count(mo[i])) ma[mo[i]] = i;
    }
    for (int i = 0; i <= n - 1; i++) {
        auto x = ranges::lower_bound(b, a[i]);
        if (x == b.end()) {
            l[i] = *(--x) - a[i];
            if (ma.count(l[i])) die[ma[l[i]]]++;
        } else if (x == b.begin()) {
            r[i] = *x - a[i];
            if (ma.count(r[i])) die[ma[r[i]]]++;
        } else {
            r[i] = *x - a[i];
            l[i] = *(--x) - a[i];
            int tem = INT_MAX;
            if (ma.count(l[i])) tem = min(tem, ma[l[i]]);
            if (ma.count(r[i])) tem = min(tem, ma[r[i]]);
            if (tem != INT_MAX) die[tem]++;
        }
    }
    for (int i = 2; i <= k; i++) die[i] += die[i - 1];
    for (int i = 1; i <= k; i++) {
        cout << n - die[i] << ' ';
    }
    cout << endl;
    return;
}

F

题目大意：现在给定 $2^n$ 头牛，它们有自己的技能等级 $a_i$ 并各自属于自己的一个栈，每个栈的总技能等级记为其中所有牛技能等级的异或和，现在会重复进行以下过程：奇数位置的栈与右边的栈进行战斗，技能等级较高的栈赢得比赛，若平局则奇数位置的赢得比赛。赢家会把自己的栈堆叠到输家上面，形成新的栈，如此直至最后只剩一个栈。

现有 $q$ 次查询，每次查询将牛 $b$ 的技能等级改变为 $c$ （注意是模拟改变，不是永久改变），问最终时有多少头牛在它上面。

数据范围： $1 \leq n \leq 18, 1 \leq q \leq 2 \cdot 10^5, 1 \leq a_i \leq 2^{30}, 1 \leq b \leq 2^n, 1 \leq c \leq 2^{30}$

思路：由于是动态查询和动态修改，很容易想到线段树。而整个过程就是类似二叉树自底向上的一个过程，只需要每次模拟需要查询的牛的所在位置，并用贡献法统计它周围栈比赛会跑到它上面的牛数量即可，经过估算发现复杂度为 $O(qn^2)$ ，显然是可以过的。

  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


template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a ^ b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }  // 若遇到固定左端点的情况，需要使用全局变量（或者传入引用）记录前缀分段最大值，加一个被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node] < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }  // 传入一个数组维护

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中第一个满足条件的下标

    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }  // 查询[ql,qr]中最后一个满足条件的下标
};
void solve() {
    int n, q, b, c;
    cin >> n >> q;
    vector<int> a((1 << n));
    for (int i = 0; i <= (1 << n) - 1; i++) cin >> a[i];
    SegmentTree tree(a);
    for (int i = 1; i <= q; i++) {
        cin >> b >> c;
        b--;
        int tem = a[b];
        tree.update(b, c);
        int tem2 = b;
        int ans = 0;
        for (int j = 0; j <= n - 1; j++) {
            int tem3 = tem2 >> j;
            if (tem3 & 1) {
                int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
                int pre2 = tree.query((tem3 - 1) << j, (tem3 << j) - 1);
                if (pre <= pre2) ans += (1 << j);
            } else {
                int pre = tree.query(tem3 << j, (tem3 << j) + (1 << j) - 1);
                int pre2 = tree.query((tem3 + 1) << j, ((tem3 + 1) << j) + (1 << j) - 1);
                if (pre < pre2) ans += (1 << j);
            }
        }
        tree.update(b, tem);
        cout << ans << endl;
    }
    return;
}

G

题目大意：给定 $n$ 个数组 $a_1,a_2,\ldots,a_n$ ，每个数组的长度为 $l_1,l_2,\ldots,l_n$ ，现在只进行一次以下操作，即选择 $1 \leq i \leq n$ 与 $1 \leq j \leq l_i$ ，将 $a_{ij}$ 添加到 $a_k ( k\not ={i})$ 中，求对于所有有序对 $(i,j,k)$ ， $\sum\limits_{i=1}^{n} \mathrm{MEX}(a_i)$ 。

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq l_i \leq 10^5, 0 \leq a_i \leq 10^6$ ， $l_i$ 之和不超过 $2 \cdot 10^5$ 。

思路：看到这里肯定考虑贡献法，首先判断取出的数会不会影响当前数组的MEX，即它是否在MEX的范围内，且是否有替代，同时考虑加入的数组中会不会影响该数组的MEX，注意加入的数不一定是让当前数组的MEX+1，完全可能是连接上两段不相干的数，因此需要预处理原始MEX和可能存在的缝合一次后的MEX，并计算贡献。

 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


void solve() {
    int n;
    cin >> n;
    vector<int> l(n);
    vector<vector<int>> a(n);
    for (int i = 0; i <= n - 1; i++) {
        cin >> l[i];
        a[i].resize(l[i]);
        for (int j = 0; j < l[i]; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> mex(n, 0);
    ll tot = 0;
    ll ans = 0;
    vector<map<int, int>> ma(n);
    map<int, int> ma2;
    for (int i = 0; i <= n - 1; i++) {
        int cnt = 0;
        for (int& p : a[i]) ma[i][p]++;
        while (ma[i].count(cnt)) cnt++;
        mex[i] = cnt;
        tot += 1LL * cnt;
        int cnt2 = cnt + 1;
        while (ma[i].count(cnt2)) cnt2++;
        ma2[cnt] += cnt2 - cnt;
    }
    for (int i = 0; i <= n - 1; i++) {
        for (int j = 0; j <= l[i] - 1; j++) {
            if (a[i][j] <= mex[i]) {
                int tem = ma2[a[i][j]];
                if (ma[i][a[i][j]] >= 2) {
                    ans += (n - 1) * tot + 1LL * tem;
                } else {
                    ans += (n - 1) * tot + 1LL * tem;
                    ans -= 1LL * (n - 1) * (mex[i] - a[i][j]);
                }
            } else {
                int tem = ma2[a[i][j]];
                ans += (n - 1) * tot + 1LL * tem;
            }
        }
    }
    cout << ans << endl;
    return;
}