球的序列

N 个编号为 1-n 的球, 每个球都有唯一的编号. 这些球被排成两种序列, 分别为 A、B 序列, 现在需要重新寻找一个球的序列 l, 对于这个子序列 l 中任意的两个球, 要求 j, k (j

样例输入

5
1 2 4 3 5
5 2 3 4 1

样例输出

2

样例说明

L 可以是 {2, 3}, 也可以是 {2, 4}

数据范围

40% N<=5000 100% N<=50000

Explanation

简单的说, 对于两个数字 j k, 若 l [j] 在 A 中比 l [k] 靠前, 那么就是说, l [j]. pos < l [k]. pos. 这样我们就把位置的关系转化成了数的关系. 首先 O (n) 预处理出他们的位置, 得到需要的数组.

然后我们会把一个 O (n ^ 4) 的问题转化成 O (n ^ 2) 的问题. 固定 A 或 B (我选择 B) 的位置, 使得 只有一个维度是不规则的. 因为最后出来的序列 A, B 一定都是单增的, 固然我们可以只固定 A 而保证答案不变. 再 O (n) 预处理一下剩下一个数组.

最后就剩下求 B [] 的最长单增子序列了, 是不是很水~

简单用了一个线段树维护, 但是水 set, map 都不行~ 是不是我哪里错了......

Example Code


// #define USE_BRUTE_FORCE
// #define USE_DEPRECATED_MAP

#include <iostream>
#include <cstdlib>
#include <cstdio>
#ifdef USE_DEPRECATED_MAP
#include <map>
#endif
#include <algorithm>

using namespace std;
const int maxn = 200010;

class SegmentTreeMini
{
public:
    int n, lb[maxn], rb[maxn], mx[maxn];
    void init(int n_) { n=1; while(n<n_)n*=2;
        for (int i=1;i<=n;i++) {int id=n-1+i;
            lb[id]=rb[id]=i;mx[id]=0;}
        for (int i=n-1;i>=1;i--) {lb[i]=lb[2*i];
            rb[i]=rb[2*i+1];mx[i]=0;}
        return ; }
    int query(int p, int l, int r) {
        if (lb[p]==l&&rb[p]==r) { return mx[p]; }
        if (rb[2*p]>=r) return query(2*p,l,r);
        else if (lb[2*p+1]<=l) return query(2*p+1,l,r);
        else return max(query(2*p,l,rb[2*p]),query(2*p+1,lb[2*p+1],r));
    } int query(int l, int r) { if(l>r) return 0; return query(1,l,r); }
    void change(int p, int l, int v) {
        if (lb[p]==l&&rb[p]==l) { mx[p]=max(mx[p],v); return ; }
        if (rb[2*p]>=l) change(2*p,l,v);
        else if (lb[2*p+1]<=l) change(2*p+1,l,v);
        else change(2*p,l,v),change(2*p+1,l,v);
        mx[p]=max(mx[2*p],mx[2*p+1]);
    } void change(int l, int v) { change(1,l,v); }
} st;

int n, r_a[maxn], r_b[maxn];
int a[maxn], b[maxn];
int dp[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &r_a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &r_b[i]);
    // Discovering their original orientations
    for (int i = 1; i <= n; i++) {
        a[r_a[i]] = i;
        b[r_b[i]] = i;
    }
    // Ordering array b by the order of a
    for (int i = 1; i <= n; i++)
        r_b[i] = b[i]; // Copying, in case of need
    for (int i = 1; i <= n; i++)
        b[a[i]] = r_b[i];
    // Building reverse index of b[] as r_b[].
    for (int i = 1; i <= n; i++)
        r_b[b[i]] = i;
    // Now the problem turns into a simpler problem:
    //     Calculate the increasing substring of b[].
    //     Maintain this using set<>.
    // Dynamic programming, with O(log n) optimization.
    dp[0] = 0;
    #ifdef USE_BRUTE_FORCE
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++) {
            if (b[j] < b[i])
            dp[i] = max(dp[i], dp[j] + 1);
        }
    #else
    #ifdef USE_DEPRECATED_MAP
    map<int, int> mp;
    mp[0] = 0;
    mp[0x4ee1dead] = 0;
    for (int i = 1; i <= n; i++) {
        int last = *--mp.upper_bound(make_pair(b[i], 0));
        int last_pos = r_b[last];
        dp[i] = dp[last_pos] + 1;
        cout << last << ' ' << last_pos << ' ' << dp[i] << endl;
        mp[b[i]] = 0;
    }
    #endif
    st.init(n);
    for (int i = 1; i <= n; i++) {
        int best = st.query(1, b[i]);
        dp[b[i]] = best + 1;
        st.change(b[i], best + 1);
    }
    #endif
    // Finding maximum result
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dp[i]);
    printf("%d\n", res);
    return 0;
}