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];
 cnt, w, sum, n;

{
    cnt = sum = ;
     ( i = ; i <= n; i++) pos[i] = ;
     ( i = ; i <= n; i++) {
         (a[i] == ) ;
         (cnt ==  || a[i] > ans[cnt]) {
            ans[++cnt] = a[i];
            pos[i] = cnt;
        }  {
             index = (ans + , ans + cnt + , a[i]) - ans;
            ans[index] = a[i];
            pos[i] = index;
        }
    }
    w = cnt;
     maxx = ;
    sum = ;
     ( i = n; i >= ; i--) {
         (!cnt) ;
         (pos[i] == cnt && maxx > a[i]) {
            cnt--;
            c[sum++] = a[i];
            maxx = a[i];
        }
    }
    (c, c + sum);
}

{
     t;
    (, &t);
     (t--) {
        (, &n);
         ( i = ; i <= n; i++) (, &a[i]);
         ( i = ; i <= n; i++) (, &b[i]);
        ();
         ( i = n; i >= ; i--) {
             index = (c, c + sum, a[b[i]]) - c;
             (c[index] != a[b[i]]) {
                d[i] = w;
                a[b[i]] = ;
                ;
            }  {
                d[i] = w;
                a[b[i]] = ;
                ();
            }
        }
         ( i = ; i <= n; i++) {
             (i == ) (, d[i]);
             (, d[i]);
        }
        ();
    }
     ;
}