D. Chat Program

题目

You’re the researcher of the International Chat Program Company (ICPC). Today, you discover the following chat history when reviewing some research data.

SUA (2022/12/04 23:01:25)

I’m out of ideas for competitive programming problems! Please give me a problem about sequences.

BOT (2022/12/04 23:01:27)

Sure. Here is a competitive programming problem about sequences.

Given an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$ and four other integers $k$, $m$, $c$ and $d$, your goal is to maximize the $k$-th largest element in the sequence.

To achieve the goal, you can perform the following operation at most once: select a continuous sub-array of length $m$ and add an arithmetic sequence with length $m$, initial term $c$ and common difference $d$ to the sub-array.

More formally, you can select an integer $p$ satisfying $1 \le p \le n - m + 1$ and add $(c + di)$ to $a_{p + i}$ for all $0 \le i < m$.

Calculate the largest possible value of the $k$-th largest element in the sequence after at most one operation.

The $k$-th largest element in the sequence is the $k$-th element in the sorted sequence after sorting all elements from the largest to the smallest. For example, the $3$rd largest element in sequence ${5, 7, 1, 9}$ is $5$, while the $3$rd largest element in sequence ${9, 7, 5, 9}$ is $7$.

SUA (2022/12/05 00:15:17)

This problem seems difficult! Please teach me the solution.

BOT (2022/12/05 00:15:30)

Sure. Firstly, we can…

[DATA EXPUNGED]

Unfortunately, parts of the chat history are lost due to a disk failure. You’re amazed at how a chat program can create a competitive programming problem. To verify whether the chat program can create valid problems, you decide to try on this problem.

思路

二分答案，如果一个数想成为数组中的第k大，那么就需要至少k-1个比他大的数存在，在check函数中，我们把比mid大的数字状态更新为1，不做考虑，所有状态为0的点在need数组中记录达到mid所需要的最小项数，现在要做的就是维护所有状态为0的点，让他们尽可能多的变成比mid大的数字，当这些数字满足>=k时，则当前的mid是满足条件的

因为等差数列是连续加在数组上的，那么不妨把这个等差数列想象成一个滑动窗口m，m的第i个数代表等差数列的第i项，在移动窗口的时候窗口尾部每扫描到一个为0的点，判断一下他的need是否小于m的尾项，如果是，就加入到一个优先队列里面（优先队列用来存储当前元素弹出的下标idx，根据idx的大小关系排序，越小的弹出时间越早），否则直接略过，在每一次挪动窗口加入值之后用while循环判断当前有多少元素已经不满足条件。遍历一遍维护优先队列的最大size即可，加上之前已经大于mid的元素个数与k进行比较。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,k,m,c,d,a[N];
bool st[N];
int need[N];
bool check(int mid){
    for(int i=1;i<=n;i++){  
        if(a[i]>=mid) st[i]=1;
        else st[i]=0;
        need[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            if(mid-a[i]<=c) need[i]=1;
            else{
                if(d==0) need[i]=1e9; //公差为0时，首项不满足，之后任何一项都不会满足，所以need[i]记录无限大
                else
                need[i]=(mid-a[i]-c+(d-1))/d+1; 
            }
        }
    }
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=1;i<=m;i++){
        if(st[i]==0&&need[i]<=i) q.push(m+(i-need[i])+1);
    }
    int ans=q.size();
    for(int i=m+1;i<=n;i++){
        if(st[i]==0&&need[i]<=m) q.push(i+(m-need[i])+1);
        while(!q.empty()&&q.top()<=i){
            q.pop();
        }
        ans=max(ans,(int)q.size());
    }
    for(int i=1;i<=n;i++){
        if(st[i]) ans++;
    }
    if(ans>=k) return 0;
    else return 1;
}
void solve()
{
    cin>>n>>k>>m>>c>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=0,r=1e17;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) r=mid-1;
        else l=mid;
    }
    cout<<l<<endl;
}
signed main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}