2024杭电多校（7） 1007. 创作乐曲【线段树预处理、dp、思维】

1007. 创作乐曲

题意

给定一个长度为 $n$ 的正整数数组 $a$，定义一个子序列是好的当且仅当：相邻元素的绝对值不超过 $k$

给出 $q$ 个询问，对每个询问 $l,r$，回答区间 $[l,r]$ 最少删除多少个元素，使得留下的数组是好的

思路

删除最少等价于留下最多，我们先考虑 $dp$：
定义 $d{p}_{i,0}$ 为不选第 $i$ 个元素的留下的最大元素个数， $d{p}_{i,1}$ 为选择第 $i$ 个元素的留下的最大元素个数

那么显然有转移：
d p i , 0 = max ⁡ { d p i − 1 , 0 , d p i − 1 , 1 } dp_{i, 0} = \max\{ dp_{i - 1,0}, dp_{i - 1,1} \} dpi,0​=max{dpi−1,0​,dpi−1,1​}
d p i , 1 = max ⁡ ∣ a i − a j ∣ ≤ k ∧ j < i { d p j , 1 } + 1 dp_{i, 1} = \max_{|a_i - a_j| \leq k \wedge j < i} \{ dp_{j, 1}\} + 1 dpi,1​=max∣ai​−aj​∣≤k∧j<i​{dpj,1​}+1

如果我们直接用线段树去存每个 $a_i$ 对应的 $dp$ 值，复杂度将达到 $qn\log n$，无法通过

考虑优化，观察一下我们会发现：$d{p}_{i,1}$ 合法的转移可以分为两类：$a_i-k\le a_j\le a_i$ 和 $a_i\le a_j\le a_i+k$，我们分别找到这两类距离 $i$ 位置最近的点 $j_1$ 和 $j_2$，我们只需要从这两个点转移即可

这是因为：对于前面同样合法的转移位置，它们其实已经包含在了 $d{p}_{j_1}$ 和 $d{p}_{j_2}$ 里，因为如果我们选择更前面的比 $a_i$ 大的，同样可以在它们之间插入 $j_1$，$j_2$ 同理。
所以我们直接从最后一个合法的位置转移过来即可，这里其实体现了 $dp$ 的包含性，更后面的 $dp$ 状态包含了前面的 $dp$ 状态

因此我们只需要预处理每个位置前面离他最近的两个分类的点即可，这个可以用线段树解决，先对所有 $a_i$ 离散化，最多只有 $O(n)$ 种取值，我们把他们映射到线段树上，下标表示相应的值，点的权值就是最后一次出现的位置，取 $\max$，动态加点即可。这是一个单点修改，区间查询最大值

时间复杂度：$O(n\log n+qn)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(int n_, std::vector<T> init_) {
        init(n_, init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(n_, std::vector(n_ + 1, v_));
    }
    template<class T>
    void init(int n_, std::vector<T> init_) {
        n = n_;
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void update(int p, int l, int r, int qp, const Info& v){
        if(l == r){
            info[p] = info[p] + v;
            return;
        }
        int m = l + r >> 1;
        if(qp <= m) update(p << 1, l, m, qp, v);
        else update(p << 1 | 1, m + 1, r, qp, v);
        pull(p);
    }
    Info query(int p, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr) return info[p];
        if(qr < l || r < ql) return Info();
        int mid = l + r >> 1;
        return query(p << 1, l, mid, ql, qr) + query(p << 1 | 1, mid + 1, r, ql, qr);
    }
};

struct Info {
    int mx = 0;
};

Info operator+(Info a, Info b) {
    return {std::max(a.mx, b.mx)};
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
        int n;
        ll m, k;
        std::cin >> n >> m >> k;
        std::vector<ll> a(n + 1);
        std::vector<ll> vec;
        fore(i, 1, n + 1){
            std::cin >> a[i];
            vec.push_back(a[i]);
        }
        std::sort(ALL(vec));
        vec.erase(unique(ALL(vec)), vec.end());
        
        auto getID = [&](ll x) -> int {
            return std::lower_bound(ALL(vec), x) - vec.begin() + 1;
        };

        int sz = vec.size();
        SegmentTree<Info> seg(sz);
        std::vector<int> pos1(n + 1, 0), pos2(n + 1, 0);
        fore(i, 1, n + 1){
            int l = getID(a[i] - k), r = std::upper_bound(ALL(vec), a[i] + k) - vec.begin();
            int id = getID(a[i]);
            pos1[i] = seg.query(1, 1, sz, l, id).mx;
            pos2[i] = seg.query(1, 1, sz, id, r).mx;
            seg.update(1, 1, sz, id, {i});
        }

        int q;
        std::cin >> q;
        std::vector<std::array<int, 2>> dp(n + 1);
        while(q--){
            int l, r;
            std::cin >> l >> r;
            fore(i, l - 1, r + 1) dp[i][0] = dp[i][1] = 0; //记得清空 dp[l - 1]
            int len = r - l + 1;
            fore(i, l, r + 1){
                dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
                dp[i][1] = 1;
                if(pos1[i] >= l) dp[i][1] = std::max(dp[i][1], 1 + dp[pos1[i]][1]);
                if(pos2[i] >= l) dp[i][1] = std::max(dp[i][1], 1 + dp[pos2[i]][1]);
            }

            std::cout << len - std::max(dp[r][0], dp[r][1]) << endl;
        }
    }
    
    return 0;
}