Problem Statement

Given a sequence \(a_1, a_2, \dots, a_n\), select elements to delete such that the remaining subsequence maximizes the count of indices \(i\) where \(a_i = i\). The goal is to compute this maximum value.

Initial Solution and Limitations

A dynamic programming approach tracks the longest subsequence satisfying \(a_j = j\) after deletions. The naive implementation uses a nested loop to check preceding elements:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> seq(n+1), dp(n+1);
    for (int i = 1; i <= n; i++) cin >> seq[i];

    int result = 0;
    for (int i = 1; i <= n; i++) {
        if (seq[i] <= i) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (seq[j] < seq[i] && (seq[i] - seq[j]) <= (i - j)) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            result = max(result, dp[i]);
        }
    }
    cout << result;
    return 0;
}

This approach has \(O(n^2)\) time complexity, which is inefficient for large \(n\) (e.g., \(n \approx 500,000\)).

Optimized Approach with Fenwick Tree

The constraints to valid predecessor are:

1. \(j < i\)
2. \(a_j < a_i\)
3. \(a_i - i \leq a_j - j\)

We sort elements by value and process them in descending order of \((a_i - i)\). A Fenwick tree maintains maximum DP values for efficient range queries.

Optimized Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

inline int lowbit(int x) { return x & -x; }

struct Element {
    int index;
    int value;
};

void update(vector<int>& tree, int pos, int val) {
    while (pos < tree.size()) {
        tree[pos] = max(tree[pos], val);
        pos += lowbit(pos);
    }
}

int query(vector<int>& tree, int pos) {
    int max_val = 0;
    while (pos > 0) {
        max_val = max(max_val, tree[pos]);
        pos -= lowbit(pos);
    }
    return max_val;
}

int main() {
    int n;
    cin >> n;
    vector<Element> elements(n+1);
    vector<int> diff(n+1), tree(n+1), dp(n+1);

    for (int i = 1; i <= n; i++) {
        cin >> elements[i].value;
        elements[i].index = i;
    }

    sort(elements.begin()+1, elements.end(), [](auto& a, auto& b) {
        return a.value == b.value ? a.index < b.index : a.value < b.value;
    });

    vector<int> unique_starts(n+1);
    for (int i = 1; i <= n; i++) {
        if (elements[i].value == elements[i-1].value) 
            unique_starts[i] = unique_starts[i-1];
        else 
            unique_starts[i] = i;
    }

    vector<pair<int, int>> deltas;
    for (int i = 1; i <= n; i++) {
        deltas.push_back({elements[i].value - elements[i].index, i});
    }
    sort(deltas.begin(), deltas.end(), greater<pair<int, int>>());

    int max_count = 0;
    for (auto& [delta, idx] : deltas) {
        if (delta > 0) continue;
        int prev_max = query(tree, unique_starts[idx] - 1);
        dp[idx] = prev_max + 1;
        update(tree, idx, dp[idx]);
        max_count = max(max_count, dp[idx]);
    }
    cout << max_count;
    return 0;
}