CF474E 【Pillars】题解

算法分析：

首先看到题目给的条件，可以想到求最长上升子序列的  做法(本人习惯用树状数组)。

设  表示以  结尾的符合题目要求的子序列的最大长度，一个  的做法是 ，其中需要满足  并且 。

但这道题的数据范围，是需要用  的做法来通过。

由于对于一个位置 ，能被转移到的位置是有限的，必须满足 ，把绝对值打开可以得到  或 ，可以发现被能转移到的区间被分为了两部分， 到  和  到给定的上界。所以我们可以维护一个线段树来记录区间最大值。

这时我们的 ​ 可以通过线段树求两个区间的最大值的最大值  来转移。

上述是查询操作，接下来看修改操作。已知当前点 ，把 ​ 作为下标， 作为值来进行修改，把影响到的节点的区间最大值进行比较并修改。

最后一步，考虑如何统计答案。由于让我们输出最长子序列的下标，我们可以另外用一个数组 ，来记录当前点的 ​ 值是由前面哪一个点转移过来的。然后一直跳  数组，用一个栈记录，最后把栈中的元素输出即可。

注意！这道题的数据范围不能直接传统线段树，需要动态开点。

总代码：

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c)  for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int M = 1e5+10;
const int maxn = 1e15;
int n,d,root,cnt,ans,anspos;
int a[M],f[M],pre[M];
struct tree{
    int ls,rs,id,val;
}t[M*40];
#define ls t[k].ls
#define rs t[k].rs
inline void pushup(int k){ //更新节点信息 
    if(t[ls].val > t[rs].val) t[k].val = t[ls].val,t[k].id = t[ls].id;
    else t[k].val = t[rs].val,t[k].id = t[rs].id;
}
inline void modify(int &k,int l,int r,int x,int val,int id){
    if(!k) k=++cnt; //需要动态开点 
    if(l == r){
        if(val > t[k].val) t[k].val = val,t[k].id = id; //更新 
        return;
    }
    int mid = (l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,val,id);
    else modify(rs,mid+1,r,x,val,id);
    pushup(k); //常规操作 
}
inline tree query(int k,int l,int r,int x,int y){
    if(!k || yreturn (tree){0,0,0,0};
    if(x<=l && r<=y) return t[k];
    int mid = (l+r)>>1;
    tree res1 = (tree){0,0,0,0},res2 = (tree){0,0,0,0};
    if(x<=mid) res1 = query(ls,l,mid,x,y);
    if(y>mid) res2 = query(rs,mid+1,r,x,y); 
    if(res1.val < res2.val) res1.val = res2.val,res1.id = res2.id; //需要找到最大值 
    return res1;
}
signed main(){
    n=read(),d=read();
    rep(i,1,n) a[i] = read();
    rep(i,1,n){
        tree tmp1 = query(root,1,maxn,1,a[i]-d);
        tree tmp2 = query(root,1,maxn,a[i]+d,maxn); //注意，是两个区间，要取这两个区间的最大值 
        if(tmp1.val < tmp2.val) swap(tmp1,tmp2); //把tmp1记为答案 
        f[i] = tmp1.val + 1; //进行dp修改 
        pre[i] = tmp1.id; //标转移到i的位置 
        if(ans < f[i]) ans=f[i],anspos=i; //最后输出的答案 
        modify(root,1,maxn,a[i],f[i],i); //需要把a[i]当成下标，f[i]当成值进行修改 
    }
    printf("%lld\n",ans);
    stack<int> s; //如上述所说，记录答案 
    for(re int i(anspos) ; i ; i=pre[i]) s.push(i); //一直跳pre就行 
    while(!s.empty()) printf("%lld ",s.top()),s.pop();
    return 0;
}