Problem A: Incremental Subarray

By examining the pattern of numbers, we observe that if the given sequence \(a\) does not form a contiguous interval, the result is always 1. Otherwise, we check the last element \(a_m\) of the sequence. The answer becomes \(n - a_m + 1\), representing the count of integers from \(a_m\) to \(n\).

#include 
using namespace std;

void processCase() {
    int totalNumbers, seqLength;
    cin >> totalNumbers >> seqLength;
    
    vector<int> sequence(seqLength);
    for (int i = 0; i < seqLength; ++i) {
        cin >> sequence[i];
    }
    
    bool isConsecutive = true;
    for (int i = 1; i < seqLength; ++i) {
        if (sequence[i] != sequence[i-1] + 1) {
            isConsecutive = false;
            break;
        }
    }
    
    if (!isConsecutive) {
        cout << 1 << "\n";
    } else {
        int lastVal = sequence[seqLength - 1];
        cout << totalNumbers - lastVal + 1 << "\n";
    }
}

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

Problem B: Incremental Path

Through simulation and pattern observation, the path for person \(i\) can be derived from person \(i-1\)'s path by removing the last point and appending two new steps. This allows us to maintain only the final two positions for each person.

We use a set to track black cells and a vector to maintain the last positions. Since paths are monotonically increasing, each cell is visited at most twice, making the simulation efficient.

#include 
using namespace std;

void processCase() {
    int peopleCount, blockedCount;
    cin >> peopleCount >> blockedCount;
    
    string cellType;
    cin >> cellType;
    cellType = " " + cellType;
    
    set<int> blockedCells;
    vector<int> blockedList(blockedCount + 1);
    for (int i = 1; i <= blockedCount; ++i) {
        cin >> blockedList[i];
        blockedCells.insert(blockedList[i]);
    }
    
    vector<int> pathHistory;
    pathHistory.push_back(1);
    
    for (int person = 1; person <= peopleCount; ++person) {
        if (pathHistory.back() != 1) {
            pathHistory.pop_back();
        }
        
        int currentPos = pathHistory.back();
        
        if (person > 1) {
            currentPos++;
            if (cellType[person - 1] == 'B') {
                while (blockedCells.count(currentPos)) {
                    currentPos++;
                }
            }
            pathHistory.push_back(currentPos);
        }
        
        currentPos++;
        if (cellType[person] == 'B') {
            while (blockedCells.count(currentPos)) {
                currentPos++;
            }
        }
        pathHistory.push_back(currentPos);
        blockedCells.insert(currentPos);
    }
    
    cout << blockedCells.size() << "\n";
    for (int cell : blockedCells) {
        cout << cell << " ";
    }
    cout << "\n";
}

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

Problem C: Incremental Stay

For a fixed \(k\), the optimal strategy is to keep \(k-1\) people in the museum continuously. The remaining person cycles through entry and exit. When one person leaves, another enters, maximizing the total occupancy time.

The contribution from the first \(k-1\) people is \(a_{2n} - a_1 + a_{2n-1} - a_2 + \ldots + a_{2n-k+2} - a_{k-1}\). The middle portion involves alternating between odd and even indexed times. We can compute answers for all \(k\) from 1 to \(n\) with \(O(1)\) transition between consecutive values.

#include 
using namespace std;
using ll = long long;

void processCase() {
    int n;
    cin >> n;
    
    vector<int> times(2 * n + 1);
    ll evenSum = 0, oddSum = 0;
    
    for (int i = 1; i <= 2 * n; ++i) {
        cin >> times[i];
        if (i % 2 == 1) {
            oddSum += times[i];
        } else {
            evenSum += times[i];
        }
    }
    
    ll accumulated = 0;
    int left = 1, right = 2 * n;
    
    for (int k = 1; k <= n; ++k) {
        cout << accumulated + evenSum - oddSum << " \n"[k == n];
        accumulated += times[right] - times[left];
        
        if (right % 2 == 0) {
            evenSum -= times[right];
            oddSum -= times[left];
        } else {
            oddSum -= times[left];
            evenSum -= times[right];
        }
        
        swap(oddSum, evenSum);
        right--;
        left++;
    }
}

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

Problem D: Grid Counting

Analyzing the constraints reveals that \((1,1)\) must be black since it satisfies both the second condition for \(k=1\) and third condition for \(k=n\). Consequently, cells \((i,1)\) for \(i \ge 2\) cannot be selected.

Extending this reasoning, only cells \((i,j)\) where \(i \le n - j + 1\) can be black. Each column must have exactly one black cell, with the row index satisfying \(i \le \min(j, n - j + 1)\).

We process rows from bottom to top. For each row \(i\), the number of available columns increases by 2 (or 1 for the middle row in odd \(n\)). Using combinations, we calculate \(\binom{\text{available}}{a_i}\) for each row.

#include 
using namespace std;

const int MOD = 998244353;

class ModularInt {
public:
    int val;
    ModularInt(int v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    ModularInt operator+(const ModularInt& other) const {
        return ModularInt(val + other.val);
    }
    ModularInt operator-(const ModularInt& other) const {
        return ModularInt(val - other.val);
    }
    ModularInt operator*(const ModularInt& other) const {
        return ModularInt(1LL * val * other.val % MOD);
    }
    ModularInt power(int exp) const {
        ModularInt result(1), base(*this);
        while (exp > 0) {
            if (exp & 1) result = result * base;
            base = base * base;
            exp >>= 1;
        }
        return result;
    }
    ModularInt inverse() const { return power(MOD - 2); }
};

class Combinatorics {
    vector<ModularInt> factorial, invFactorial;
public:
    Combinatorics(int n) : factorial(n + 1), invFactorial(n + 1) {
        factorial[0] = ModularInt(1);
        for (int i = 1; i <= n; ++i) {
            factorial[i] = factorial[i-1] * ModularInt(i);
        }
        invFactorial[n] = factorial[n].inverse();
        for (int i = n - 1; i >= 0; --i) {
            invFactorial[i] = invFactorial[i+1] * ModularInt(i+1);
        }
    }
    ModularInt comb(int n, int r) {
        if (r < 0 || r > n) return ModularInt(0);
        return factorial[n] * invFactorial[r] * invFactorial[n-r];
    }
};

void processCase() {
    int n;
    cin >> n;
    vector<int> rowCounts(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> rowCounts[i];
    }
    
    Combinatorics comb(n + 5);
    ModularInt result(1);
    int availableCols = 0;
    
    for (int row = n; row >= 1; --row) {
        if (2 * row == n + 1) {
            availableCols++;
        } else if (2 * row <= n) {
            availableCols += 2;
        }
        
        if (availableCols < rowCounts[row]) {
            cout << 0 << "\n";
            return;
        }
        
        result = result * comb.comb(availableCols, rowCounts[row]);
        availableCols -= rowCounts[row];
    }
    
    if (availableCols != 0) result = ModularInt(0);
    cout << result.val << "\n";
}

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

Problem E: Limited Edition Shop

We define \(dp_{i,j}\) as the maximum total value when Alice has purchased the first \(i\) items and Bob has purchased the first \(j\) items. A naive \(O(n^2)\) DP is too slow, requiring optimization.

The key insight involves the ordering constraint: if Alice selects items in set \(S\), then for any \(x \notin S\) and \(y \in S\), if \(posa_x < posa_y\) in Alice's sequence, we must have \(posb_x < posb_y\) in Bob's sequence.

Using a segment tree to maintain the second dimension, we can efficiently query the maximum over range \([0, pos_{a_i}-1]\) and perform range additions. This reduces the complexity to \(O(n \log n)\).

#include 
using namespace std;
using ll = long long;

class SegTree {
    vector<ll> tree, lazy;
    int size;
    
    void pushDown(int node) {
        if (lazy[node] != 0) {
            tree[node*2] += lazy[node];
            tree[node*2+1] += lazy[node];
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
            lazy[node] = 0;
        }
    }
    
    void rangeAdd(int node, int start, int end, int l, int r, ll val) {
        if (l > end || r < start) return;
        if (l <= start && end <= r) {
            tree[node] += val;
            lazy[node] += val;
            return;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        rangeAdd(node*2, start, mid, l, r, val);
        rangeAdd(node*2+1, mid+1, end, l, r, val);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    
    ll rangeMax(int node, int start, int end, int l, int r) {
        if (l > end || r < start) return LLONG_MIN;
        if (l <= start && end <= r) return tree[node];
        pushDown(node);
        int mid = (start + end) / 2;
        return max(rangeMax(node*2, start, mid, l, r),
                   rangeMax(node*2+1, mid+1, end, l, r));
    }
    
    void pointUpdate(int node, int start, int end, int pos, ll val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        if (pos <= mid) pointUpdate(node*2, start, mid, pos, val);
        else pointUpdate(node*2+1, mid+1, end, pos, val);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    
public:
    SegTree(int n) : size(n), tree(4*n+5, 0), lazy(4*n+5, 0) {}
    
    void addRange(int l, int r, ll val) { rangeAdd(1, 1, size, l, r, val); }
    ll queryMax(int l, int r) { return rangeMax(1, 1, size, l, r); }
    void updatePoint(int pos, ll val) { pointUpdate(1, 1, size, pos, val); }
};

void processCase() {
    int n;
    cin >> n;
    
    vector<int> value(n+1), aliceSeq(n+1), bobSeq(n+1), posInBob(n+1);
    for (int i = 1; i <= n; ++i) cin >> value[i];
    for (int i = 1; i <= n; ++i) cin >> aliceSeq[i];
    for (int i = 1; i <= n; ++i) {
        cin >> bobSeq[i];
        posInBob[bobSeq[i]] = i + 1;
    }
    
    SegTree seg(n + 2);
    
    for (int i = 1; i <= n; ++i) {
        ll bestVal = seg.queryMax(1, posInBob[aliceSeq[i]]);
        seg.addRange(1, posInBob[aliceSeq[i]] - 1, value[aliceSeq[i]]);
        bestVal = max(bestVal, seg.queryMax(1, posInBob[aliceSeq[i]]));
        seg.updatePoint(posInBob[aliceSeq[i]], bestVal);
    }
    
    cout << seg.queryMax(1, n + 1) << "\n";
}

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