专栏文章

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

qqdl66666666
P14306题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mini8vxu
此快照首次捕获于
2025/12/02 02:51
3 个月前
此快照最后确认于
2025/12/02 02:51
3 个月前
查看原文

一篇线段树题解

题意

给你一个序列，你可以选择其中一些数，定义这个子序列的和谐度为区间长度乘 kk 减去区间的极差。形式化： (r−l+1)×k−(max⁡(al,...,ar)−min⁡(al,..,ar))(r - l + 1) \times k - (\max(a_l,...,a_r) - \min(a_l,..,a_r))
让你选出一个子序列，使得和谐度最大，输出这个最大值。

思路

转化1

考虑子序列不好做，我们进行排序，这样我们一定选一个区间作为答案。
考虑证明：对于 [l,r][l,r]，将整个区间都选和只选 l,rl,r 的极差一样，但前面的选法会使区间长度更大，故选择整个区间一定更优。
还有一个显然的结论，一个区间的最大值和最小值放在了这个区间的两端。

转化2

那根据类似扫描线的思想，先枚举一维，再用数据结构维护另一维。
这里我们枚举区间右端点 RR，用线段树维护 [1,R−1][1,R-1] 中以 RR 为右端点的区间的和谐度最大值。
我们考虑加入一个右端点会使前面的数如何更新和谐度。
设原区间长度为 lenlen，原极差为 pp，加入的数为 aia_i，则新区间的和谐度为
(len+1)×k−p−(ai−ai−1)=len×k−p+k−ai+ai−1(len+1)\times k - p - (a_i-a_{i-1}) = len\times k - p + k - a_i + a_{i-1}
所以我们每添加一个数，就将线段树中维护的和谐度都加 k−ai+ai−1k - a_i + a_{i-1}，并将这个数的初始和谐度 kk 插入线段树。

实现

维护区间最大值，支持区间加的线段树。
具体：对序列排序，枚举每个位置，对全局加 k−ai+ai−1k-a_i+a_{i-1}，然后在 ii 插入值 kk，ansans 记录当前的全局最大值。复杂度 O(Tnlog⁡n)O(Tn\log n)。
注意多测清空。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...