HDU 6635 Nonsense Time 题解：逆向思维求解动态 LIS

题目描述

You are given a permutation p1, p2, ..., pn of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element p[ki] will become available.

For each i, find the longest increasing subsequence among available elements after the first i stages.

输入输出

Input

The first line of the input contains an integer T (1 ≤ T ≤ 3), denoting the number of test cases.

In each test case, there is one integer n (1 ≤ n ≤ 50000) in the first line, denoting the size of permutation.

In the second line, there are n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n), denoting the permutation.

In the third line, there are n distinct integers k1, k2, ..., kn (1 ≤ ki ≤ n), describing each stage.

It is guaranteed that p1, p2, ..., pn and k1, k2, ..., kn are generated randomly.

Output

For each test case, print a single line containing n integers, where the i-th integer denotes the length of the longest increasing subsequence among available elements after the first i stages.

解题思路

题目要求在元素逐个激活的过程中，每次查询当前可用元素的最长上升子序列（LIS）长度。正向动态维护较为困难，考虑采用逆向思维。

1. 逆向处理：从所有元素都可用开始，逐步移除元素。倒序处理时，如果移除的元素不在当前的 LIS 中，则 LIS 长度不变；如果移除的元素在 LIS 中，则需要重新计算 LIS。
2. 复杂度分析：最坏时间复杂度为 O(n^2 * log n)，但由于数据是随机生成的，平均复杂度可优化至 O(n * sqrt(n) * log n)。
3. 实现细节：使用贪心策略配合二分查找（lower_bound）来维护 LIS。记录每个数在 LIS 中的位置，以便判断被移除的数是否关键。

参考代码

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

typedef long long ll;
const int MAX = 1e6 + 10;
int a[MAX], b[MAX], c[MAX], pos[MAX], ans[MAX], d[MAX];
int cnt, w, sum, n;

void solve() {
    cnt = sum = 0;
    for (int i = 0; i <= n; i++) pos[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) continue;
        if (cnt == 0 || a[i] > ans[cnt]) {
            ans[++cnt] = a[i];
            pos[i] = cnt;
        } else {
            int index = lower_bound(ans + 1, ans + cnt + 1, a[i]) - ans;
            ans[index] = a[i];
            pos[i] = index;
        }
    }
    w = cnt;
    int maxx = 5201314;
    sum = 0;
    for (int i = n; i >= 1; i--) {
        if (!cnt) break;
        if (pos[i] == cnt && maxx > a[i]) {
            cnt--;
            c[sum++] = a[i];
            maxx = a[i];
        }
    }
    sort(c, c + sum);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        solve();
        for (int i = n; i >= 1; i--) {
            int index = lower_bound(c, c + sum, a[b[i]]) - c;
            if (c[index] != a[b[i]]) {
                d[i] = w;
                a[b[i]] = 0;
                continue;
            } else {
                d[i] = w;
                a[b[i]] = 0;
                solve();
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i == 1) printf("%d", d[i]);
            else printf(" %d", d[i]);
        }
        puts("");
    }
    return 0;
}

总结

本题通过逆向思维将动态增加问题转化为动态删除问题，利用随机数据的特性降低了期望复杂度。核心在于快速判断被移除元素对 LIS 的影响，并适时更新状态。