专栏文章

题解：P10093 [ROIR 2022] 礼物 (Day 2)

MMeta_Morph
P10093题解参与者 1已保存评论 0

文章操作

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

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

[ROIR 2022] 礼物 (Day 2) 题解

博客园哦哦哦：[ROIR 2022] 礼物 (Day 2) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

链表。

分析

首先看到数据范围 k≤min⁡(100,n)k\le\min(100,n)，说明复杂度与 kk 有关，那么我们就可以考虑暴力一点地解决这个问题。
一开始我们可以想到按顺序插入数值，这样会有较好的性质，比如从大到小插入一个 uu 时，包含 uu 和它之前插入的值作为区间前 kk 大的情况其实只有 kk 种。
假设 k=2k=2，以 1/01/0 分别代表插入和没插入的值，1\color{red}1 表示我们这次插入的值：
000100001000000001000010000000{\color{blue}1}0000{\color{red}1}00000000{\color{green}1}000010000
那么其实可以分为两种情况：
  1. 包括 1{\color{blue}1} 和 1{\color{red}1}。
  2. 包括 1{\color{red}1} 和 1{\color{green}1}。
我们可以考虑用求前缀和数组区间 min⁡,max⁡\min,\max 优化，那么一次只要遍历 O(k)O(k) 就可以解决。
但是这样实现较为麻烦，插入需要 set<int> 之类的，维护区间 min⁡,max⁡\min,\max 需要 ST 表之类的，我们可以转化问题：把从大到小插入改为从小到大删除。
那么删除只需维护链表，维护区间 min⁡,max⁡\min,\max 也可以直接在链表上一起维护，代码变得非常简洁，复杂度 O(nk)O(nk)。
最后，注意恶心的 k=0k=0。

代码

CPP
constexpr int N(2e5+10);

int n,m;
int a[N],idx[N],pre[N],nxt[N];
ll ans;
ll mn[N],mx[N],sum[N];

signed main() {
	/*DE("Input");*/
	scanf("%d%d",&n,&m);
	FOR(i,1,n)scanf("%d",&a[i]);
	FOR(i,1,n)sum[i]=sum[i-1]+a[i];
	if(!m) {
		ans=-LINF;
		ll mn(0);
		FOR(i,1,n)tomax(ans,sum[i]-mn),tomin(mn,sum[i]);
		printf("%lld\n",ans);
		return 0;
	}
	/*DE("Init");*/
	FOR(i,1,n)idx[i]=i;
	sort(idx+1,idx+n+1,[](int x,int y) { return a[x]<a[y]; });
	pre[0]=0,nxt[0]=1,pre[n+1]=n,nxt[n+1]=0;
	FOR(i,1,n)pre[i]=i-1,nxt[i]=i+1;
	FOR(i,0,n)mn[i]=mx[i]=sum[i];
	/*DE("Solve");*/
	FOR(i,1,n-m+1) {
		const int &u(idx[i]);
		int l(u);
		for(int j(m); l&&j>0; l=pre[l],--j);
		int r(l);
		ll cnt(0);
		for(int j(m); j>0; cnt+=a[r=nxt[r]],--j);
		for(; l<=u&&r<=n; cnt-=a[l=nxt[l]],cnt+=a[r=nxt[r]])tomax(ans,mx[r]-mn[l]-cnt);
		tomin(mn[pre[u]],mn[u]),tomax(mx[pre[u]],mx[u]);
		pre[nxt[u]]=pre[u],nxt[pre[u]]=nxt[u];
	}
	/*DE("Output");*/
	printf("%lld\n",ans);
	return 0;
}

评论

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

正在加载评论...