Problem A: The Man who became a God

For a sequence (a) of length (n), define the cost of a segment ([l, r]) as (f(l, r) = \sum_{i=l}^{r-1} |a_i - a_{i+1}|). We need to partition the entire sequence into (k) contiguous segments to maximize the sum of segment costs.

The total cost of the whole sequence is (f(1, n) = \sum_{i=1}^{n-1} |a_i - a_{i+1}|). Cutting between positions (x) and (x+1) removes the term (|a_x - a_{x+1}|) from this total. Therefore, partitioning into (k) segments means removing exactly (k-1) absolute differences. To maximize the sum, we should remove the (k-1) smallest differences. So we just sort the (n-1) differences and take the sum of the smallest (n-k) of them.

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

const int MAX = 1005;
int a[MAX];

void solve() {
    int n, k;
    cin >> n >> k;
    int prev;
    cin >> prev;
    for (int i = 1; i < n; ++i) {
        int cur;
        cin >> cur;
        a[i] = abs(prev - cur);
        prev = cur;
    }
    sort(a + 1, a + n);
    int ans = 0;
    for (int i = 1; i <= n - k; ++i)
        ans += a[i];
    cout << ans << '\n';
}

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

Problem B: Hamon Odyssey

For an array (a), define (f(l,r) = a_l & a_{l+1} & \dots & a_r). We want to split the array into the maximum number of contiguous segments such that the sum of segment values is minimized.

Let (g = f(1,n)). The minimum possible sum of segment values is exactly (g) (since AND over a superset is never larger than AND over a subset). If (g \neq 0), the only way to achieve sum (g) is to not split at all, i.e., one segment. If (g = 0), we can greedily extend a segment until its AND becomes zero, then start a new segment. This yields the maximal number of segments.

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

const int MAX = 200005;
int a[MAX];

void solve() {
    int n;
    cin >> n;
    int total_and;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i == 0) total_and = a[i];
        else total_and &= a[i];
    }
    if (total_and != 0) {
        cout << "1\n";
        return;
    }
    int cur = a[0], cnt = 0;
    for (int i = 0; i < n; ++i) {
        cur &= a[i];
        if (cur == 0) {
            ++cnt;
            if (i + 1 < n) cur = a[i + 1];
        }
    }
    cout << cnt << '\n';
}

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

Problem C: Vampiric Powers, anyone?

Given array (a), for each position (i) we need to compute the maximum XOR over all subarrays ending at (i), i.e., (\max_{1 \le j \le i} (a_j \oplus a_{j+1} \oplus \dots \oplus a_i)). The answer is the maximum among all such values.

A naive (O(n^2)) algorithm would be too slow ((n \le 10^5)). However, (a_i < 2^8 = 256), so the XOR values are bounded by 255. We can maintain a boolean array vis of size 256 that marks all prefix XOR values seen so far. For each new prefix XOR x, we can check all previously seen prefix XORs y and update the answer with x ^ y. This runs in (O(256 \cdot n)), which is about (2.56 \times 10^7), acceptable.

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

const int M = (1 << 8) - 1;
const int MAXN = 100005;
bool seen[M + 1];
int a[MAXN];

void solve() {
    int n;
    cin >> n;
    fill(seen, seen + M + 1, false);
    seen[0] = true;
    for (int i = 0; i < n; ++i) cin >> a[i];
    int pref = 0, ans = -1;
    for (int i = 0; i < n; ++i) {
        pref ^= a[i];
        for (int v = 0; v <= M; ++v) {
            if (seen[v]) ans = max(ans, pref ^ v);
        }
        seen[pref] = true;
    }
    cout << ans << '\n';
}

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

Problem D: Professor Higashikata

We have a binary string (s) of length (n). We also have (m) intervals ([l_i, r_i]). The concatenation (t(s) = t_1 + t_2 + \dots + t_m) contains each interval's substring. We may swap any two characters in (s) arbitrarily. After each query (flipping a single position (x_i)), we need to find the minimum number of swaps required to make (t(s)) lexicographically maximal.

Observation: To maximize lexicographic order, all '1's should be placed as early as possible in (t(s)). Each position (s_i) may appear in several intervals. But for any two intervals, if (i < j) and (s_i) appears in both, then fixing (s_i) to '1' already gives '1' in both intervals; there is no benefit to treating them separately. In fact, each position in (s) is assigned to the earliest interval containing it. So we can compress the postiions into a sequence (t') of length (g) (the number of distinct positions in order of first appearance).

We maintain a Fenwick tree over (t') that counts '1's in this compressed string. Let (S) be the total number of '1's in (s). Then best we can do is to have (\min(g, S)) ones at the beginning of (t'). The number of swaps needed is exactly that target number minus the count of ones already among the first (\min(g, S)) positions of (t'). Each flip update changes (S) and toggles a position in the Fenwick tree if that position is present in (t').

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

const int MAX = 200005;

char s[MAX];
int n, m, q;
vector<pair<int,int>> intervals;
int first_id[MAX];          // first interval index containing position i (0 if none)
int compressed_pos[MAX];    // position in compressed string (0 if absent)
char compressed[MAX];       // actual characters in compressed order
int bit[MAX], g;

void add(int idx, int delta) {
    for (; idx <= g; idx += idx & -idx)
        bit[idx] += delta;
}

int sum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx)
        res += bit[idx];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    cin >> (s + 1);
    intervals.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> intervals[i].first >> intervals[i].second;
    
    // Assign each position to the earliest interval containing it
    vector<int> start_at[n+2];
    vector<int> end_at[n+2];
    for (int i = 0; i < m; ++i) {
        int L = intervals[i].first - 1;
        int R = intervals[i].second;
        start_at[L].push_back(i);
        end_at[R].push_back(i);
    }
    set<int> active;
    for (int i = 1; i <= n; ++i) {
        for (int idx : start_at[i-1]) active.insert(idx);
        for (int idx : end_at[i]) active.erase(idx);
        if (active.empty()) first_id[i] = -1;
        else first_id[i] = *active.begin();
    }
    
    // Build compressed string
    vector<int> in_compressed[m];
    for (int i = 1; i <= n; ++i) {
        if (first_id[i] != -1) {
            in_compressed[first_id[i]].push_back(i);
        }
    }
    g = 0;
    for (int i = 0; i < m; ++i) {
        for (int pos : in_compressed[i]) {
            compressed[++g] = s[pos];
            compressed_pos[pos] = g;
        }
    }
    
    int total_ones = 0;
    for (int i = 1; i <= n; ++i)
        if (s[i] == '1') ++total_ones;
    
    for (int i = 1; i <= g; ++i)
        if (compressed[i] == '1') add(i, 1);
    
    while (q--) {
        int x;
        cin >> x;
        if (s[x] == '1') {
            s[x] = '0';
            --total_ones;
            if (compressed_pos[x])
                add(compressed_pos[x], -1);
        } else {
            s[x] = '1';
            ++total_ones;
            if (compressed_pos[x])
                add(compressed_pos[x], 1);
        }
        int target = min(g, total_ones);
        cout << target - sum(target) << '\n';
    }
    return 0;
}