Interval Inversion Count

Given an array of length n with elements bounded by a small constant (≤ 50), we need to answer m queries of the form: count the number of inversions inside subarray [l, r]. A naive O(n2) per query is too slow, and a Mo’s algorithm solution, while feasible for moderate constraints, will not handle the worst case. The key observation is that we can precompute prefix inversions if we manage to subtract cross‑inversions efficiently.

Let inv[i] be the total number of inversions in the first i elements, and cnt[i][v] be how many times value v appears among the first i elements. For a query [l, r], the inversions inside [l, r] equal inv[r] - inv[l-1] - cross, where cross counts pairs with the first element in [1, l−1] and the second in [l, r] that form an inversion. We compute cross by iterating values from largest to smallest, maintaining a running sum of the occurrences in the left prefix. For each value v, the left prefix contributes sum_left_so_far × (cnt[r][v] - cnt[l-1][v]). This gives an O(n · maxA + m · maxA) solution, easily fitting the limits.

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

const int MAXN = 1e6 + 5;
const int MAXV = 55;
int pref_cnt[MAXN][MAXV];
long long inv_prefix[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        ++x; // shift to 1-based value
        for (int v = 1; v < MAXV; ++v)
            pref_cnt[i][v] = pref_cnt[i-1][v];
        int greater_cnt = 0;
        for (int v = x + 1; v < MAXV; ++v)
            greater_cnt += pref_cnt[i][v];
        inv_prefix[i] = inv_prefix[i-1] + greater_cnt;
        pref_cnt[i][x]++;
    }
    while (m--) {
        int l, r; cin >> l >> r;
        long long cross = 0, left_acc = 0;
        for (int v = MAXV - 1; v >= 1; --v) {
            cross += left_acc * (pref_cnt[r][v] - pref_cnt[l-1][v]);
            left_acc += pref_cnt[l-1][v];
        }
        cout << inv_prefix[r] - inv_prefix[l-1] - cross << '\n';
    }
    return 0;
}

Permutation with Limited Moves

We are given a permutation of {1,…,n} and an integer m. Elements outside the range [1,m] must be moved either to position 1 or to position m, and whenever an element moves to one of these fixed positions, the previous occupant shifts cyclically. The goal is to minimize the total number of unit‑distance moves. A useful insight is that for any number i not yet inside [1,m], the optimal move is always to bring it direct to position 1 or m. This leads to a DP state dp[i][0] = minimal cost when i is placed at position 1, and dp[i][1] for position m.

Transitions are not simply from i to i+1, because once i is fixed, several subsequent numbers might already lie inside [1,m] and need no move. Hence we jump to the smallest number k > i that is currently outside [1,m] and treat it as the next decision point. This k can be found with a segment tree that maintains the minimum value in a sliding window over the circular arrangement. After processing each i, we set its position to a large sentinel so it won’t be chosen again. The DP thus runs in O(n log n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 500005;
const int INF = 1e9;

int n, m;
int pos[MAXN * 2];
ll dp[MAXN][2];
struct SegTree {
    vector<int> tree;
    int sz;
    SegTree(int n) : sz(n) { tree.assign(2 * n, INF); }
    void build() {
        for (int i = 0; i < sz; ++i) tree[i + sz] = pos[i + 1];
        for (int i = sz - 1; i; --i) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    int query(int l, int r) {
        int res = INF;
        for (l += sz - 1, r += sz - 1; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, tree[l++]);
            if (!(r & 1)) res = min(res, tree[r--]);
        }
        return res;
    }
    void update(int p, int val) {
        p += sz - 1;
        tree[p] = val;
        for (p >>= 1; p; p >>= 1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
    }
};

int dist_on_circle(int a, int b) {
    if (a <= 0) a += n;
    if (a > n) a -= n;
    int fwd = (a >= b ? a - b : a + n - b);
    int bwd = (b >= a ? b - a : n - a + b);
    return fwd < bwd ? fwd : -bwd;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        pos[x] = i;
        pos[x + n] = i;
    }
    SegTree seg(2 * n);
    seg.build();
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0; // virtual 0 at position 1
    ll ans = LLONG_MAX;
    for (int i = 0; i < n; ++i) {
        int loc_i = (i == 0 ? 1 : pos[i]);
        // from dp[i][0] (i at position 1)
        int nxt = seg.query(loc_i + m, loc_i + n - 1);
        if (nxt == INF) ans = min(ans, dp[i][0]);
        else {
            int loc_nxt = pos[nxt];
            int shift1 = dist_on_circle(loc_nxt - dist_on_circle(loc_i, 1), 1);
            dp[nxt][0] = min(dp[nxt][0], dp[i][0] + abs(shift1));
            shift1 = dist_on_circle(loc_nxt - dist_on_circle(loc_i, 1), m);
            dp[nxt][1] = min(dp[nxt][1], dp[i][0] + abs(shift1));
        }
        // from dp[i][1] (i at position m)
        nxt = seg.query(loc_i + 1, loc_i + n - m);
        if (nxt == INF) ans = min(ans, dp[i][1]);
        else {
            int loc_nxt = pos[nxt];
            int shift2 = dist_on_circle(loc_nxt - dist_on_circle(loc_i, m), 1);
            dp[nxt][0] = min(dp[nxt][0], dp[i][1] + abs(shift2));
            shift2 = dist_on_circle(loc_nxt - dist_on_circle(loc_i, m), m);
            dp[nxt][1] = min(dp[nxt][1], dp[i][1] + abs(shift2));
        }
        if (i) {
            seg.update(pos[i], INF);
            seg.update(pos[i] + n, INF);
        }
    }
    ans = min({ans, dp[n][0], dp[n][1]});
    cout << ans << '\n';
    return 0;
}

Camellia – Maximum XOR with One Increment

We are given n integers. We may choose a subset, XOR them together, and then we are allowed to add 1 to any one of the chosen numbers (i.e., increment a value before XORing, if it is part of the subset). The goal is to maximize the final XOR result. The plus‑one operation is most beneficial when it causes a long carry chain, i.e. when the number ends with many consecutive 1‑bits. Hence we want to construct a XOR that ends with a long suffix of 1’s, so that incrementing that element triggers a cascade of bit flips. This suggests building a linear basis that operates from the least significant bit upward, i.e. a low‑priority basis. After building it, we check from the most significant bit downward whether we can achieve a suffix of ones of length len. If possible, we replace the suffix with the carry effect and output the result.

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

ll basis[61];

void insert_low(ll x) {
    for (int b = 0; b <= 60; ++b) {
        if ((x >> b) & 1) {
            if (basis[b]) x ^= basis[b];
            else { basis[b] = x; return; }
        }
    }
}

ll build_suffix(int len) {
    ll res = 0;
    for (int b = 0; b <= len; ++b) {
        int need = (b == len) ? 0 : 1;
        if (((res >> b) & 1) == need) continue;
        if (basis[b]) res ^= basis[b];
        else return -1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    ll overall_xor = 0;
    for (int i = 0; i < n; ++i) {
        ll v; cin >> v;
        overall_xor ^= v;
        insert_low(v);
    }
    for (int len = 60; len >= 0; --len) {
        if ((overall_xor >> len) & 1) continue;
        ll pat = build_suffix(len);
        if (pat != -1) {
            overall_xor ^= ((1LL << (len + 1)) - 1);
            cout << overall_xor << '\n';
            return 0;
        }
    }
    cout << overall_xor + 1 << '\n';
    return 0;
}

Medians with Element Deletions

We process a permutation of 1…n by successively deleting elements in reverse order and maintaining the median of the current set. Inserting an element and keeping the median is hard to do in O(1), but deleting one element is easier if we work on a sorted structure. Since the domain is exactly {1,…,n} and all values are distinct, a linked list over the value domain gives an ordered representation. We maintain the predecessor and successor of each value. Starting from the whole set, we know the initial median. As we delete the element originally at position i (in the deletion sequence), we adjust the median by at most one step to the left or right depending on whether the deleted element was smaller, equal, or larger than the current median. The total complexity is O(n).

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

const int MAXN = 1e7 + 5;
const int MOD = 998244353;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;

int p[MAXN], h[MAXN];
struct Node { int prev, next; } dom[MAXN]; // domain list

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, a;
    cin >> n >> a;
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int i = 1; i <= n; ++i) {
        a = (1LL * a * MOD + MOD7) % MOD9;
        swap(p[i], p[a % i + 1]);
    }
    h[0] = 1;
    for (int i = 1; i <= n; ++i) {
        dom[i].prev = i - 1;
        dom[i].next = i + 1;
        h[i] = 1LL * h[i-1] * 19 % MOD;
    }
    int median = (n + 1) / 2;
    int smaller = median - 1, bigger = n - median;
    long long ans = 0;
    for (int i = n; i >= 1; --i) {
        // maintain correct median position
        while (smaller + 1 < (i + 1) / 2) {
            median = dom[median].next;
            ++smaller; --bigger;
        }
        while (smaller + 1 > (i + 1) / 2) {
            median = dom[median].prev;
            --smaller; ++bigger;
        }
        ans = (ans + 1LL * (median % MOD) * h[i]) % MOD;
        int val = p[i];
        if (val < median) --smaller;
        else if (val == median) {
            if (dom[median].prev == 0) {
                median = dom[median].next;
                --bigger;
            } else {
                median = dom[median].prev;
                --smaller;
            }
        } else --bigger;
        // delete from domain list
        dom[dom[val].prev].next = dom[val].next;
        dom[dom[val].next].prev = dom[val].prev;
    }
    cout << ans << '\n';
    return 0;
}

Construct – Equation xp² = ab + bc + ac

We need to find positive integers a, b, c satisfying xp² = ab + bc + ac. Rearranging gives xp² + a² = (a + b)(a + c). A natural attempt is to set a = p, yielding (x+1)p² = (p+b)(p+c), so we can choose b = x+1−p and c = p²−p. This works when x ≥ p.

When x < p, we try to reduce the effective modulus. Let m = p mod (x+1); then 0 ≤ m ≤ x. Setting a = m, the equation modulo x+1 still holds, giving b = x+1−m and c = (xp² + m²)/(x+1) − m. This yields positive integers unless p = x+1 (where m = 0) making a possibly non‑positive. For the special case p = x+1, a separate construction a = 6, b = p−3, c = p²−4p+6 works for p > 3 (otherwise no solution exists). The solution is entirely analytical and runs in O(1) per test case.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll x, p; cin >> x >> p;
        if (x >= p) {
            cout << p << ' ' << x + 1 - p << ' ' << p*p - p << '\n';
        } else {
            if (p == x + 1) {
                if (p <= 3) cout << "-1\n";
                else cout << 6 << ' ' << p - 3 << ' ' << p*p - 4*p + 6 << '\n';
            } else {
                ll m = p % (x + 1);
                cout << m << ' ' << x + 1 - m << ' '
                     << (x * p * p + m * m) / (x + 1) - m << '\n';
            }
        }
    }
    return 0;
}