最大连边数量

题目大意

分析

看到不相交，如果做过树状数组的练习，这个条件满足某种偏序关系 (经验之谈qwq，相关知识不甚了解)

刚开始想到贪心对于每个 $A[i]$ ,可以处理出来 $B$ 中,使得$abs(A[i]-B[j] <= 4)$ 的 $j$，存入 $g[i]$

然后顺序遍历 $i$，贪心取g[i]，保证大于取的 $g[i-1]$

出现问题！

第 $i$ 个数可能不连边

那么连 $or$ 不连,考虑 $dp$

$dp[i]$ 表示为 考虑到$b$中第 $i$ 个位置时的最大连边数

枚举 $A[i]$, 对每个$A[i]$,枚举可以连边的 $g[i][j]$

因为更新 $j$ 只与 $[1,j-1]$有关,且 $i$ 是顺序枚举,这就保证了连边的两条线不会相交

用树状数组记录最大值去更新 $dp[j]$ 即可

注意查询和更新树状数组的顺序

应该先查询所有的 $j$ 之后，再去更新 $j$

Code

int n;
int f[100005];
int lwb(int x) {
    return x & -x;
}
int tr[100005];

void add(int p,int v){
    for(int i = p;i <= n;i+=lwb(i)){
        tr[i] = max(tr[i],v);
    }
}
int ask(int p){
    int res = 0;
    for(int i = p;i;i-=lwb(i)){
        res = max(res,tr[i]);
    }
    return res;
}

signed main()
{
    _nt;
    cin >> n;
    map<int,int> d;
    vector<int> a(n+1),b(n+1);
    for(int i = 1;i <= n;i++) cin >> a[i];   
    for(int i = 1;i <= n;i++) cin >> b[i],d[b[i]] = i;

    vector<int> g[n+1];
    for(int i = 1; i <= n;i++){
        for(int j = max(1LL,a[i]-4LL);j <= min(a[i]+4,n);j++){
            g[i].push_back(d[j]);
        }
    }   
    for(int i = 1;i <= n;i++) sort(g[i].begin(),g[i].end());

    for(int i = 1;i <= n;i++){
        for(auto j:g[i])    f[j] = max(f[j],ask(j-1) + 1);
        for(auto j:g[i])    add(j,f[j]);
    }
    // int res = 0;
    // for(auto i:g[n]){
    //     res = max(res,f[i]);
    // }
    // cout << res << endl;
    cout << *max_element(f+1,f+1+n) << endl;
    // int res = 0;
    // int last = 0;
    // for(int i = 1;i <= n;i++){
    //     auto p = upper_bound(g[i].begin(),g[i].end(),last);
    //     if(p != g[i].end()){
    //         // cout << res << endl;
    //         res++;
    //         last = *p;
    //     }
    //  }
    //cout << res << endl;
    return 0;
}