题解：P6993 [NEERC2014] Improvements

· · 题解

P6993 [NEERC2014] Improvements 题解

前置知识

树状数组。

题目分析

首先我们可以知道，对于移动一个点等价于删除一个点，这个是好理解的，那么原题面转化为删去最少的点使得剩下的点连线合法。

考虑最后剩下的合法点序列的形态长什么样。

我们规定箭头指的方向表示后面节点的编号大于前面结点的编号。发现任意一个节点都保证一定是后缀点的最大或最小的 x，不然就不合法。

对于一个节点，他下一个节点可能往左跳或者往右跳，往右跳，使得这段序列的编号持续递增，往左跳使得在它左边的点的编号持续递减。

对于任意一个合法序列，按照 x 重排后，发现它的编号是一段上升子序列和一段下降子序列，其实我们答案就是枚举每一个点的最长上升子序列和最长下降子序列，最后取出最大值即可。

最长上升子序列和最长下降子序列可以用树状数组预处理出来。

时间复杂度为 O(n\log n)。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<random>
#include<chrono>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
const int N=2e5+10; 
int n,a[N],ans=0;
int f[N],g[N];
struct DS{
    int tr[N*2];
    void init(){
        for(int i=1;i<=N;i++)tr[i]=0;
    }
    void add(int x,int k){
        for(;x<=N;x+=x&-x)tr[x]=max(tr[x],k);
    }
    int ask(int x){
        int res=0;
        for(;x;x-=x&-x)res=max(res,tr[x]);
        return res;
    }
}bit;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=bit.ask(a[i])+1;
        bit.add(a[i],f[i]);
    }
    bit.init();
    for(int i=1;i<=n;i++)a[i]=n-a[i]+1;
    for(int i=1;i<=n;i++){
        g[i]=bit.ask(a[i])+1;
        bit.add(a[i],g[i]);
    }
    for(int i=1;i<=n;i++)ans=max(f[i]+g[i]-1,ans);
    cout<<ans;
    return 0;
}