CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

A - Jagged Swaps

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n;
        rep (i, 1, n) cin >> a[i];
        while (true) {
            bool f = 0;
            rep (i, 2, n - 1) if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                f = 1;
            }
            if (!f) break;
        }
        bool f = 1;
        rep (i, 1, n) if (i != a[i]) {
            f = 0;
            break;
        }
        cout << (f ? "YES\n" : "NO\n");
    }
    return 0;
}

B - AB Flipping

正反各来一次

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> s + 1;
        int ans = 0;
        rep (i, 1, n) f[i] = 1;
        per (i, n - 1, 1) {
            if (s[i] == 'A' && s[i + 1] == 'B') {
                ++ans;
                swap(s[i], s[i + 1]);
                f[i] = 0;
            }
        }
        rep (i, 1, n - 1) {
            if (s[i] == 'A' && s[i + 1] == 'B' && f[i]) {
                ++ans;
                swap(s[i], s[i + 1]);
                f[i] = 0;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

C - Matching Arrays

每次以贪心地增加/减少匹配项

const int N = 2e5 + 5;
 
int n, m, _, k, cas;
int a[N], b[N], c[N], d[N];
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m;
        rep (i, 1, n) cin >> a[i], c[i] = i;
        rep (i, 1, n) cin >> b[i];
        sort(c + 1, c + 1 + n, [&](int x, int y) { return a[x] < a[y]; });
        sort(b + 1, b + 1 + n);
        int cnt = 0;
        rep (i, 1, n) cnt += a[c[i]] > b[i];
        if (cnt < m) {
            set<PII> q;
            rep (i, 1, n) if (a[c[i]] <= b[i]) {
                if (!q.empty() && q.begin()->fi < a[c[i]]) {
                    int pp = q.begin()->se;
                    swap(b[i], b[pp]);
                    ++cnt;
                    if (cnt == m) break;
                    q.erase(q.begin());
                    q.emplace(b[pp], pp);
                } else {
                    q.emplace(b[i], i);
                }
            }
        } else if (cnt > m) {
            set<PII> q;
            rep (i, 1, n) if (a[c[i]] > b[i]) {
                if (!q.empty() && b[i] >= q.begin()->fi) {
                    int pp = q.begin()->se;
                    swap(b[i], b[pp]);
                    --cnt;
                    if (cnt == m) break;
                    q.erase(q.begin());
                }
                q.emplace(a[c[i]], i);
            }
        }
        if (cnt == m) {
            rep (i, 1, n) d[c[i]] = b[i];
            cout << "YES\n";
            rep (i, 1, n) cout << d[i] << ' ';
            cout << '\n';
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

D - Ones and Twos

考察奇偶性，考虑从头/尾丢弃 item 来使得剩余的子数组和等于所求

当头尾丢弃的 item 和是偶数时，必定有解，每次也偶数的从头/尾丢弃偶数即可（或者头尾一起各丢一个 1）
当头尾丢弃的 item 和是奇数是，先从数组头 or 尾贪心的选一个方向丢一个 1, 就可以转成情况 1 了（前提剩余 sum 可以凑出所求和）

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m;
        int s = 0;
        set<int> st;
        rep (i, 1, n) {
            cin >> a[i], s += a[i];
            if (a[i] == 1) st.emplace(i);
        }
        rep (i, 1, m) {
            int op; cin >> op;
            if (op == 2) {
                int x, y; cin >> x >> y;
                if (a[x] == 1) st.erase(x);
                s -= a[x]; a[x] = y;
                if (a[x] == 1) st.emplace(x);
                s += a[x];
            } else {
                int x; cin >> x;
                if (s < x) cout << "NO\n";
                else if (s == x) cout << "YES\n";
                else {
                    int z = s - x;
                    if (!(z & 1)) cout << "YES\n";
                    else if (!st.empty() && z >= (min(*st.begin() - 1, n - *st.rbegin()) << 1) + 1) cout << "YES\n";
                    else cout << "NO\n";
                } 
            }
        }
    }
    return 0;
}

E - Permutation Sorting

每个数字移动的距离不会超过 n, 为了方便计算，选择拆环，让 a[n + 1 ~ n * 2] = a[1 ~ n]

每个位置移动的绝对距离是 \(s_i\), 即 \((i + h_i − 1) % n =a_i - 1\)

然后就是考虑路径上哪些点 j 可以跳过，即 \(i < j < i + h_i and (i < a_j < i + h_i or i < a_j + n < i + h_i)\)

或者说对于点 i 的移动路径是 [l, r] (l = i, (r - 1) mod n + 1 = \(a_i\)), 他路径上可以跳过的点就是路径被 [l, r] 包含的路径

然后就是找个数据结构维护单点修改，区间查询路径上可以跳过的点数就好了

const int N = 1e6 + 5;
 
int n, m, _, cas;
int a[N], c[N << 1], ans[N];
 
void add(int x, int k) { for (; x <= n << 1; x += -x & x) c[x] += k; }
 
int ask(int x) { int ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans; }
 
int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n;
        memset(c, 0, sizeof(int) * n << 1);
        vector<PII> e;
        rep (i, 1, n) {
            cin >> a[i];
            if (i <= a[i]) {
                e.pb(i, a[i]);
                e.pb(i + n, a[i] + n);
            }
            else e.pb(i, a[i] + n);
        }
        sort(e.begin(), e.end(), greater<PII>());
        for (auto [l, r]: e) {
            if (l <= n) {
                ans[a[l]] = r - l - ask(r) + ask(l - 1);
            }
            add(r, 1);
        }
        rep (i, 1, n) cout << ans[i] << ' ';
        cout << '\n';
    }
    return 0;
}