CodeForces - 474E dp+离散+线段树优化

以你之姓@ 2022-05-14 12:19 174阅读 0赞

[这个题][Link 1]

跟[这个题][Link 2]类似，都是一维dp,n^2复杂度，但是需要优化，

感觉这种题数据小点1e4的话优化成nsqrt（n）就可以，1e5的话，要优化成nlog(n)，

这个题是用线段树维护的最大值。因为一个数只能由前面1~val\[i\]-d，或者val\[i\]+d~INF转移过来，

所以我只要查询值在这个范围之内dp值得最大值就好，因为值是在1e15得范围，所以需要离散化。

因为要输出路径，所以用pre记录前缀

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    int dp[N], n, cnt, pre[N];
    ll d, val[N], hs[N<<2];
    struct node{
        int v, pos;
    }tree[N<<4];
    
    void push_up(int rt){
        if(tree[rt<<1].v>=tree[rt<<1|1].v){
            tree[rt].v=tree[rt<<1].v;
            tree[rt].pos=tree[rt<<1].pos;
        }
        else{
            tree[rt].v=tree[rt<<1|1].v;
            tree[rt].pos=tree[rt<<1|1].pos;
        }
    }
    
    void build(int rt, int l, int r){
        tree[rt].v=0; tree[rt].pos=-1;
        if(l==r)
            return;
        int mid=(l+r)>>1;
        build(rt<<1, l, mid);
        build(rt<<1|1, mid+1, r);
        push_up(rt);
    }
    
    node query(int rt, int l, int r, int L, int R){
        if(L<=l && r<=R)
            return tree[rt];
        int mid=(l+r)>>1;
        node it=(node){0, -1}, tmp;
        if(mid>=L)
            it=query(rt<<1, l, mid, L, R);
        if(mid<R){
            tmp=query(rt<<1|1, mid+1, r, L, R);
            if(tmp.v>it.v) it=tmp;
        }
        return it;
    }
    
    void upd(int rt, int l, int r, int tar, int v, int pos){
    
        if(l==tar && r==tar){
            if(v>tree[rt].v){
                tree[rt].v= v;
                tree[rt].pos=pos;
            }
            return;
        }
        int mid=(l+r)>>1;
        if(tar<=mid)
            upd(rt<<1, l, mid, tar, v, pos);
        else
            upd(rt<<1|1, mid+1, r, tar, v, pos);
        push_up(rt);
    }
    
    void add(int &a, node b, int c){
        if(b.v+1>a){
            a=b.v+1;
            pre[c]=b.pos;
        }
    }
    
    int main(){
        scanf("%d%lld", &n, &d);
    
        for(int i=1; i<=n; i++){
            scanf("%lld", &val[i]);
            hs[++cnt]=val[i];
            if(val[i]-d>0) hs[++cnt]=val[i]-d;
            hs[++cnt]=val[i]+d;
        }
    
        sort(hs+1, hs+1+cnt);
        cnt=unique(hs+1, hs+1+cnt)-hs-1;
        build(1, 1, cnt);
    
        for(int i=1; i<=n; i++){
    
            int up=lower_bound(hs+1, hs+1+cnt, val[i]+d)-hs;
            node tmp = query(1, 1, cnt, up, cnt);
            add(dp[i], tmp, i);
    
            if(val[i]-d>0){
                int down=lower_bound(hs+1, hs+1+cnt, val[i]-d)-hs;
                tmp=query(1, 1, cnt, 1, down);
                add(dp[i], tmp, i);
            }
            int pos=lower_bound(hs+1, hs+1+cnt, val[i])-hs;
    
            upd(1, 1, cnt, pos, dp[i], i);
        }
    
        int ans=0, pr;
        for(int i=1; i<=n; i++){
            if(ans<dp[i]){
                ans=dp[i]; pr=i;
            }
        }
        printf("%d\n", ans);
        stack<int> s;
        while(pr!=-1){
            s.push(pr);
            pr=pre[pr];
        }
        while(!s.empty()){
            printf("%d", s.top());
            s.pop();
            if(s.empty()) putchar('\n');
            else putchar(' ');
        }
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/474/E
[Link 2]: https://blog.csdn.net/du_lun/article/details/82497267