题解：P14306 【MX-J27-T3】旋律

· · 题解

一篇线段树题解

题意

给你一个序列，你可以选择其中一些数，定义这个子序列的和谐度为区间长度乘 k 减去区间的极差。形式化：

(r - l + 1) \times k - (\max(a_l,...,a_r) - \min(a_l,..,a_r))

让你选出一个子序列，使得和谐度最大，输出这个最大值。

思路

转化1

考虑子序列不好做，我们进行排序，这样我们一定选一个区间作为答案。

考虑证明：对于 [l,r]，将整个区间都选和只选 l,r 的极差一样，但前面的选法会使区间长度更大，故选择整个区间一定更优。

还有一个显然的结论，一个区间的最大值和最小值放在了这个区间的两端。

转化2

那根据类似扫描线的思想，先枚举一维，再用数据结构维护另一维。

这里我们枚举区间右端点 R，用线段树维护 [1,R-1] 中以 R 为右端点的区间的和谐度最大值。

我们考虑加入一个右端点会使前面的数如何更新和谐度。
设原区间长度为 len，原极差为 p，加入的数为 a_i，则新区间的和谐度为

(len+1)\times k - p - (a_i-a_{i-1}) = len\times k - p + k - a_i + a_{i-1}

所以我们每添加一个数，就将线段树中维护的和谐度都加 k - a_i + a_{i-1}，并将这个数的初始和谐度 k 插入线段树。

实现

维护区间最大值，支持区间加的线段树。

具体：对序列排序，枚举每个位置，对全局加 k-a_i+a_{i-1}，然后在 i 插入值 k，ans 记录当前的全局最大值。复杂度 O(Tn\log n)。

注意多测清空。

#include<bits/stdc++.h>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const int N = 2e5 + 10;
template<typename TY>
inline void read(TY &s){
    ll 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();
    }
    s = x * f;
}
int c,T; 
int n;
ll k,ans;
ll maxn[N<<2],tag[N<<2],a[N]; 
inline void push_up(int rt){
    maxn[rt] = max(maxn[ls],maxn[rs]);
}
void build(int rt,int l,int r){
    maxn[rt] = 0; tag[rt] = 0;
    if(l == r) return;
    build(lson); build(rson);
}
inline void add(int rt,int l,int r,ll v){
    maxn[rt] += v; tag[rt] += v;
}
inline void push_down(int rt,int l,int r){
    if(!tag[rt]) return;
    add(lson,tag[rt]); add(rson,tag[rt]);
    tag[rt] = 0;
}
void modify(int rt,int l,int r,int ql,int qr,ll v){
    if(ql <= l && r <= qr){
        add(rt,l,r,v);
        return;
    }
    push_down(rt,l,r);
    if(ql <= mid) modify(lson,ql,qr,v);
    if(mid + 1 <= qr) modify(rson,ql,qr,v);
    push_up(rt);
}
void update(int rt,int l,int r,int x,ll v){
    if(l == r){
        maxn[rt] = v;
        return;
    }
    push_down(rt,l,r);
    if(x <= mid) update(lson,x,v);
    else update(rson,x,v);
    push_up(rt);
}
int main(){
//  freopen("melody4.in","r",stdin);
    read(c); read(T);
    while(T--){
        read(n); read(k);
        for(int i=1;i<=n;i++){
            read(a[i]);
        }
        sort(a+1,a+n+1);
        build(1,1,n);
        ans = 0;
        for(int i=1;i<=n;i++){
            modify(1,1,n,1,n,k - a[i] + a[i-1]);
            update(1,1,n,i,k);
            ans = max(ans,maxn[1]);
        }
        cout << ans << "\n"; 
    }
    return 0;
}