Codeforces Round 994 (Div. 2)部分题解

C

一道很具有启发性的构造题，我们可以推广到一般的简单图情况：

以任意顺序遍历所有遍历结点并将其赋值为其已赋值邻居的 \(mex\) ，因为一条边上的两个结点值一定不同，所以后赋值的不会影响前赋值的 \(mex\) ，所以这样构造是正确的。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve()
{
    int n, x, y; cin >> n >> x >> y;
    x--, y--;;
    vector<int>a(n);
    for (int i = 0; i < n; i++)
    {
        set<int>s;
        if (i)s.insert(a[i - 1]);
        if (i == n - 1)s.insert(a[0]);
        if (y == i)s.insert(a[x]);
        while (s.count(a[i]))a[i]++;
    }
    for (int i = 0; i < n; i++)cout << a[i] << ' ';
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

E

妙妙思维题：

先将数组均分四段并通过 3 次查询找到 \(x\) 位于哪一段，同时我们也可以知道 \(k\) 和 \(n/4\) 的大小关系。

具体的：如果出现 2 个以上 0，说明 \(k>n/4\) ，反之 \(k\leq n/4\) 。同时 \(x\) 位于与众不同的那段。

然后正常二分 \(k\) 。对于 \(\leq n/2\) 的 check 根据前面 4 次询问的信息选择一定不包含 \(x\) 的前缀或后缀询问一次即可。同理，对于 \(>n/2\) 的 check 我们选择一定包含 \(x\) 的前缀或后缀询问一次。

实测可以确定不超过 33 次查询。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int ask(int l, int r)
{
    cout << "? " << l << ' ' << r << endl;
    int res; cin >> res;
    return res;
}
//a = 0 0 0 0 0 1 0 0
//k = 6
void solve()
{
    int n; cin >> n;
    int cnt[2] = {0}, v[4];
    for (int i = 1, j = 0; i <= (n / 4) * 3; i += n / 4) {
        v[j] = ask(i, i + n / 4 - 1);
        cnt[v[j++]]++;
    }
    if (cnt[1] == 0)cnt[1]++, v[3] = 1;
    if (cnt[0] == 0)cnt[0]++, v[3] = 0;
    bool tag = (cnt[1] == 1);
    for (int i = 0; i < 4; i++)v[i] = (v[i] == tag);
    auto check = [&](int x)->bool{
        if (x >= n / 2) {
            if (v[0] + v[1] == 1)return ask(1, x) == 0;
            else return ask(n - x + 1, n) == 0;
        }
        else{
            if (v[0] + v[1] == 0)return ask(1, x) == 1;
            else return ask(n - x + 1, n) == 1;
        }
    };
    int l = 2, r = n - 1;
    if (tag)l = n / 4 + 1;
    else r = n / 4;
    while (l < r)
    {
        int mid = l + r  >> 1;
        if (check(mid))r = mid;
        else l = mid + 1;
    }
    cout << "! " << l << endl;
}

int main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

F

首先来拆解一下题中给出的式子 \(mex(b_1,b_2,...,b_n)-(b_1|b_2|...|b_n)=1\) 。简单根据 \(mex\) 的性质分析一下可以知道 \(mex(b_1,b_2,...,b_n)\) 一定是 2 的幂次。

那我们就按照 \(mex\) 的取值分 \(logn\) 种情况来情况，对于期望 \(mex=2^i\) 的情况，我们将 \(\geq 2^i\) 的点设为断点，由贪心可以确定我们选择的区间一定与断点或边界相邻。同时我们还需要确定区间的 \(mex\) 为 \(2^i\) 。

将值插入权值线段树，我们可以通过权值线段树上二分以 \(O(logn)\) 的复杂度求出 \(mex\) 。具体的：每个结点维护相应区间各值出现次数的最小值。

注意修改过程只会不断增大，也就是不断地将点设置为断点。这个过程我们不好实现，但是我们反过来看就是不断地将断点取消，合并区间，这个过程可以线段树合并。朴素的修改就是单点查询。

然后还需要动态维护所有\(mex=2^i\) 的区间的长度的最大值，这个可以用 \(multiset\) 维护，细节很多，有几个注意的地方：

• 合并区间后要删除原区间在 \(multiset\) 中的值。
• 避免同一个区间多次往 \(multiset\) 中加入值。

时间复杂度为 \(O(nlog^2n)\) ，空间复杂度为\(O(nlogn)\) 。

如果用 \(map\) 维护区间所有值和相应的 \(mex\) ，朴素的修改 \(mex\) 单调不增，而对于合并，可以考虑启发式合并。\(mex\) 移动次数不会超过启发式合并的次数。时间复杂度为 \(O(nlog^3n)\) 。

代码通过线段树合并实现：

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 10, M = 1e7;
int n, q, ans[N];
pair<int, int>c[N];
ll a[N], b[N];
int ln[M], rn[M], pos[N], tot, cnt[M], rt[N], sz[N];
bool st[N];
int find(int x) {
    if (pos[x] != x)pos[x] = find(pos[x]);
    return pos[x];
}

void insert(int &u, int l, int r, int x, int t)
{
    if (!u)u = ++tot;
    if (l == r) {
        cnt[u] += t;
        return;
    }
    int mid = l + r >> 1;
    if (x > mid)insert(rn[u], mid + 1, r, x, t);
    else insert(ln[u], l, mid, x, t);
    cnt[u] = min(cnt[ln[u]], cnt[rn[u]]);
}

int merge(int u, int v, int l, int r)
{
    if (!u || !v)return u + v;
    if (l == r) {
        cnt[u] += cnt[v];
        return u;
    }
    int mid = l + r >> 1;
    ln[u] = merge(ln[u], ln[v], l, mid);
    rn[u] = merge(rn[u], rn[v], mid + 1, r);
    cnt[u] = min(cnt[ln[u]] , cnt[rn[u]]);
    return u;
}

int query(int u, int l, int r)
{
    if (l == r)return l;
    int mid = l + r >> 1;
    if (cnt[ln[u]] == 0)return query(ln[u], l, mid);
    else return query(rn[u], mid + 1, r);
}

void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y;
        c[i] = make_pair(x, y);
        a[x] += y;
        ans[i] = 0;
    }
    memcpy(b, a, sizeof a);

    for (int i = 0; (1 << i) <= n; i++) {
        //>=(1<<i)的设为断点
        memcpy(a, b, sizeof a);
        for (int j = 1; j <= tot; j++)ln[j] = rn[j] = cnt[j] = 0;
        for (int j = 0; j <= n; j++)rt[j] = sz[j] = st[j] = 0;
        tot = 0, rt[0] = ++tot;
        multiset<int>s; s.insert(0);
        for (int j = 1; j <= n; j++)
        {
            if (a[j] >= (1 << i)) {
                pos[j] = j;
                continue;
            }
            pos[j] = pos[j - 1], sz[pos[j]]++;
            insert(rt[pos[j]], 0, n, a[j], 1);
        }

        for (int j = 1; j <= n; j++)
        {
            if (st[pos[j]])continue;
            if (query(rt[pos[j]], 0, n) == (1 << i))s.insert(sz[pos[j]]), st[pos[j]] = 1;
        }
        for (int j = q; j; j--)
        {
            ans[j] = max(ans[j], *s.rbegin());

            auto [x, y] = c[j];
            if (a[x] >= (1 << i)) {
                a[x] -= y;

                if (a[x] < (1 << i)) {
                    int nx = find(pos[x - 1]);
                    if (st[nx])s.erase(s.find(sz[nx]));
                    if (st[x])s.erase(s.find(sz[x]));
                    rt[nx] = merge(rt[nx], rt[pos[x]], 0, n);

                    sz[nx] += sz[pos[x]] + 1, pos[x] = nx;
                    insert(rt[nx], 0, n, a[x], 1);
                    if (query(rt[nx], 0, n) == (1 << i))s.insert(sz[pos[nx]]), st[nx] = 1;
                }
            }
            else {
                pos[x] = find(pos[x]);
                insert(rt[pos[x]], 0, n, a[x], -1);
                a[x] -= y;
                insert(rt[pos[x]], 0, n, a[x], 1);
                if (query(rt[pos[x]], 0, n) == (1 << i)){
                    if(!st[pos[x]])s.insert(sz[pos[x]]), st[pos[x]] = 1;
                }
                else if (st[pos[x]])s.erase(s.find(sz[pos[x]])), st[pos[x]] = 0;//cout<<s.count(sz[pos[x]])<<"!\n";
            }

        }
    }
    for (int i = 1; i <= q; i++)cout << ans[i] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)solve();
    return 0;
}