---
url: /algo/ccc5kkak/index.md
---
## A. Perfect Root

有点抽象，赛时直接输出 $1\sim n$ 就对了（应该就是输出 $n$ 个不同正整数）。

```cpp title="A.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cout << i + 1 << " ";
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
        cout << "\n";
    }
    return 0;
}
```

## B. Prefix Max

由于只能更改一次，选择将最大的值与第一个值替换，那么每一次 $\max$ 贡献累加一定是最大的。

```cpp title="B.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    int n;
    cin >> n;
    vector<int> vi(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vi[i];
    }
    int maxs = vi[0];
    int index = 0;
    for (int i = 1; i < n; i++)
    {
        if (vi[i] > maxs)
        {
            index = i;
            maxs = vi[i];
        }
    }
    swap(vi[0], vi[index]);
    vector<int> prefixmax(n);
    prefixmax[0] = vi[0];
    for (int i = 1; i < n; i++)
    {
        prefixmax[i] = max(vi[i], prefixmax[i - 1]);
    }
    int sums = 0;
    for (int i = 0; i < n; i++)
    {
        sums += prefixmax[i];
    }
    cout << sums;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
        cout << "\n";
    }
    return 0;
}
```

## C. Shifted MEX

对于集合的 $\text{MEX}$ 来说，由于数组移位，从 $0$ 开始的连续区间大小就是 $\text{MEX}$ 的值，所以我们考虑去重排序后，寻找最长连续子区间。

```cpp title="C.cc" :collapsed-lines
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;

int lcis(const vector<int> &a)
{
    if (a.empty())
        return 0;

    int ans = 1;
    int cur = 1;

    for (int i = 1; i < (int)a.size(); ++i)
    {
        if (a[i] == a[i - 1] + 1)
        {
            cur++;
        }
        else
        {
            cur = 1;
        }
        ans = max(ans, cur);
    }

    return ans;
}
void sol()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    auto it = unique(arr.begin(), arr.end());
    arr.erase(it, arr.end());
    int t = lcis(arr);
    cout << t;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
        cout << "\n";
    }
    return 0;
}
```

## D. OutOfMemoryError

本题如果每次选择超出直接归复原数组，会导致超时（我就 tle 了一发），正确的做法是懒维护所有版本，当超出当前值时，撤销原来的更改保留从当前开始往后的更改，最后更新数组。

```cpp title="C.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;

void sol()
{
    int n, m, h;
    cin >> n >> m >> h;
    vector<int> acp(n);
    vector<int> a(n);
    vector<int> luv(n, 0);
    int cv = 1;

    for (int i = 0; i < n; i++)
    {
        cin >> acp[i];
    }

    for (int i = 0; i < m; i++)
    {
        int b, c;
        cin >> b >> c;
        int idx = b - 1;

        int current_val;
        if (luv[idx] == cv)
        {
            current_val = a[idx];
        }
        else
        {
            current_val = acp[idx];
        }

        if (current_val + c > h)
        {
            cv++;
        }
        else
        {
            a[idx] = current_val + c;
            luv[idx] = cv;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (luv[i] == cv)
        {
            cout << a[i];
        }
        else
        {
            cout << acp[i];
        }
        cout << " ";
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
        cout << "\n";
    }
    return 0;
}
```

## E. The Robotic Rush

设当前机器人所在的位置在 $a\_i$，记录其左侧尖刺在 $\ell\_i$，右侧尖刺在 $r\_i$，它到左侧尖刺的距离为 $d\_{\ell} = a\_i - \ell\_i$，到右侧尖刺的距离为 $d\_r = r\_i - a\_i$。

我们使用 `std::vector` 存取排序的的尖刺数组，并使用 `std::lower_bound` 以 $O(\log m)$ 的复杂度找到其左右邻居，存储每个机器人死亡的哈希表，然后根据每一次的 $L,R$ 字符串去计算偏移量判断有没有机器人似了，具体判断方法是是否当前的偏移量 `offset` 大于等于左边或右边允许的 $d\_{\ell},d\_r$；并记录当前似了的时间，存入 `death_time` 数组。

最后排序后遍历 $1\sim k$ 的 `LR` 字符串，决定每一次操作似了的机器人个数。总复杂度为 $O((n+m+k) \log (n+m))$。

> 比赛用 set, unordered\_set 全 tle

```cpp title="E.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a, b;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    for (int i = 0; i < m; i++)
    {
        int tmp;
        cin >> tmp;
        b.push_back(tmp);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    string s;
    cin >> s;

    vector<int> first_reach(2 * k + 1, k + 1);
    int curr_pos = 0;
    for (int i = 1; i <= k; i++)
    {
        if (s[i - 1] == 'L')
            curr_pos--;
        else
            curr_pos++;

        if (first_reach[curr_pos + k] == k + 1)
        {
            first_reach[curr_pos + k] = i;
        }
    }
    vector<int> death_times;
    for (int i : a)
    {
        auto it = lower_bound(b.begin(), b.end(), i);

        int d_death = k + 1;

        if (it != b.end())
        {
            ll dist_r = *it - i;
            if (dist_r <= k)
            {
                d_death = min(d_death, first_reach[dist_r + k]);
            }
        }

        if (it != b.begin())
        {
            ll dist_l = i - *prev(it);
            if (dist_l <= k)
            {
                d_death = min(d_death, first_reach[-dist_l + k]);
            }
        }

        if (d_death <= k)
        {
            death_times.push_back(d_death);
        }
    }
    int death_ptr = 0;
    sort(death_times.begin(), death_times.end());
    for (int i = 1; i <= k; i++)
    {
        while (death_ptr < death_times.size() && death_times[death_ptr] <= i)
        {
            death_ptr++;
        }
        cout << n - death_ptr << " ";
    }
    cout << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }
    return 0;
}
```

## F. BattleCows

> 我不到 0 秒就想到了用线段树，你也来试试吧！

线段树存两个区间参数，一个区间 `xor`，另一个是赢家来自于什么方向（相同左边赢）。然后自底向上维护，如果到第 $k$ 层牛输了，那么在它顶上的牛应当有 $2^n-2^k$，结束。

```cpp title="F.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void sol()
{
    int n, q;
    cin >> n >> q;
    int numc = 1 << n;
    vector<ll> a(numc);
    for (int i = 0; i < numc; ++i)
    {
        cin >> a[i];
    }
    vector<ll> xor_segtree(2 * numc);
    for (int i = 0; i < numc; i++)
    {
        xor_segtree[numc + i] = a[i];
    }
    for (int i = numc - 1; i > 0; i--)
    {
        xor_segtree[i] = xor_segtree[2 * i] ^ xor_segtree[2 * i + 1];
    }

    while (q--)
    {
        int b;
        ll c;
        cin >> b >> c;
        b--;

        ll original_val = a[b];
        ll diff = original_val ^ c;

        int curr_id = numc + b;
        ll cows_above = 0;

        for (int h = 0; h < n; ++h)
        {
            int sib_id = curr_id ^ 1;

            ll skill_u = xor_segtree[curr_id] ^ diff;
            ll skill_v = xor_segtree[sib_id];

            bool u_is_left = (curr_id % 2 == 0);

            if (u_is_left)
            {
                if (skill_v > skill_u)
                {
                    cows_above += (1LL << h);
                }
            }
            else
            {
                if (skill_v >= skill_u)
                {
                    cows_above += (1LL << h);
                }
            }

            curr_id /= 2;
        }
        cout << cows_above << "\n";
    }
}

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

## G. Mixing MEXes

WIP.

## H. BattleCows 2

WIP.