2024杭电多校7——1007创作乐曲

也是好久没补题了，欠了好多好多,我的评价是加训

题目如下: 文章插图 官方题解: 官方题解一如既往的简洁， $对于不会做的人要读懂真的挺难$

首先询问最少删除多少音符(一般来说不太好处理)，我们可以考虑它的对立面，最多保留多少字符这是比较好处理的我们可以尝试着想出 $d p$ 的方程就是 $d p_{i, 0} = ma x {d p_{i - 1, 0}, d p_{i - 1, 1}}$ $d p_{i, 1} = ma x {d p_{j, 1} ： ∣ a_{i} - a_{j} ∣ \leq k} + 1$ $d p [i] [0]$ 表示前i个字符中，对与第i个字符删除保留的最多字符个数， $d p [i] [1]$ 同理， $1$ 代表不删除。

这样并不是很好dp，但是通过题解中发现的性质我们可以在 $O (n q + n l o g n)$ 时间内解决问题.

那么题解的性质是什么意思呢，就是说 $d p [i] [1]$ 的最优解仅可能被两个位置更新,即在 $[a_{i} - k, a_{i}]$ 中离 $a_{i}$ 最近的点 $a_{j_{1}}$ 所在的索引 $j_{1}$ ,和在 $[a_{i}, a_{i} + k]$ 中离 $a_{i}$ 最近的点 $a_{j_{2}}$ 所在的索引 $j_{2}$ .

为什么呢？比如说 $[a_{i} - k, a_{i}]$ 中 $a_{c}$ 更新了 $d p$ 值，并且 $c < j_{1}$ ,那么它也会尝试去更新 $j_{1}$ 位置的 $d p$ 值，如果 $j_{1}$ 位置的 $d p$ 值没有被更新，二者作用等价，如果更新了，那么用 $j_{1}$ 位置的 $d p$ 值更新可以使得结果更大，所以有那样一个结论.

所以我们可以用线段树维护当前遍历到 $i$ 时， $[a_{i} - k, a_{i}]$ 和 $[a_{i}, a_{i} + k]$ 离 $a_{i}$ 最近的点 $a_{j_{2}}$ 所在的索引 $J$ .每次dp的时候用线段树查询即可，dp的时间复杂度为 $O (n l o g n)$

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;

const int maxn = 1e5+10;
int n,q;
i64 m,k;
int dp[maxn][2]={0};
inline int query(int p,int l,int r,int x,int y,vector<int>&tree){
    if(x<=l&&r<=y) return tree[p];
    int mid = (l+r)>>1;
    int ans = 0;
    if(x<=mid) ans = max(ans,query(p*2,l,mid,x,y,tree));
    if(y>mid) ans = max(ans,query(p*2+1,mid+1,r,x,y,tree));
    return ans;
}

inline void update(int p,int l,int r,int x,int num,vector<int>&tree){
    if(l==r){
        tree[p] = num;
        return;
    }
    int mid = (l+r)>>1;
    if(x<=mid) update(p*2,l,mid,x,num,tree);
    else update(p*2+1,mid+1,r,x,num,tree);
    tree[p] = max(tree[p*2],tree[p*2+1]);
}

inline void solve(){
    cin>>n>>m>>k;
    vector<i64>a(n+1);
    vector<i64>b;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        b.emplace_back(a[i]);
    }

    sort(b.begin(),b.end());
    int len =b.erase(unique(b.begin(),b.end()),b.end())-b.begin();
    auto find = [&](i64 x){
        return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
    };

    vector<int> tree((len+1)<<2,0);
    vector<int> L(n+1,0),R(n+1,0);
    for(int i = 1;i<=n;++i){
        int l = find(a[i]-k),r = upper_bound(b.begin(),b.end(),a[i]+k)-b.begin(),now  = find(a[i]);
        L[i] = query(1,1,len,l,now,tree);
        R[i] = query(1,1,len,now,r,tree);
        update(1,1,len,now,i,tree);
    }
    cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        for(int i = l-1;i<=r;++i) dp[i][0]=dp[i][1]=0;
        for(int i = l;i<=r;++i){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = 1;
            if(L[i]>=l&&L[i]<=r) dp[i][1] = max(dp[L[i]][1]+1,dp[i][1]);
            if(R[i]>=l&&R[i]<=r) dp[i][1] = max(dp[R[i]][1]+1,dp[i][1]);
        }
        cout<<r-l+1-max(dp[r][0],dp[r][1])<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

新学到的知识，在q里面开固定长度的vector会超时. 离散化的处理手法，因为我的线段树索引要从1开始用所以，离散化的时候用的是lower_bound(...)+1,对于左界来说这样没有问题，但是对于右界来说就有问题，如果我的右界不在离散化数组里，那么lower_bound(...)本身就相当于已经映射好的正确的离散化右界，+1会出错，这个画个图立得