【题解】洛谷P2048 [NOI2010]超级钢琴

题目

洛谷P2048[NOI2010]超级钢琴

题解

题目简化后即求前k大的子区间。先求前缀和s[],枚举子区间的左端点l,再找最优的右端点r(即枚举s[l-1],再找符合条件的最大的s[r]),找最大的s[r]的过程即求静态区间最大值的过程,采用ST表。将上一步找出的子区间放入优先队列中维护,接下来每次取出一个区间和最大的元素,计入答案,并求与其左端点相同,s[r]第二大的区间。求次大的s[r]时,只需先找出最大的s[r]的位置,然后在它的左侧和右侧分别用ST表求s[r]的最大值,然后都作为候选答案加入到优先队列中。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月5日 下午3:04

【小白解析】
此题题解较好理解。需注意,

求次大的s[r]时,只需先找出最大的s[r]的位置,然后在它的左侧和右侧分别用ST表求s[r]的最大值,然后都作为候选答案加入到优先队列中。

对应的是

if(x.rmin<=x.max_p1) q.push((music){x.l,x.rmin,x.max_p1,RMQ(x.rmin,x.max_p1),s[RMQ(x.rmin,x.max_p1)]s[x.l]});

if(x.rmax>=x.max_p+1) q.push((music){x.l,x.max_p+1,x.rmax,RMQ(x.max_p+1,x.rmax),s[RMQ(x.max_p+1,x.rmax)]s[x.l]});

的判断。