题目描述

blablabla

样例

blablabla

由yxc大佬的讲解我们发现越大的x他的子孙也大，我们需要开3个队列，一个存放原队列，一个存放分割左边队列，一个存放切割右边队列，有关队列单调性的证明在下方已给出，那么我们发现队列是单调递减的（即队头就是最大值），然后关于每个时刻递增q的问题，如何正确处理呢？有个比较好的方法就是记录偏移量，但是在将最长的蚯蚓分裂的时候要注意分裂的两条蚯蚓该时刻是不会加上q的，所以我们要多减一个q。
证明链接：
https://www.acwing.com/solution/content/7209/

算法

(单调队列优化)

时间复杂度 $O(m)$

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=7000010;
int n,m,q,u,v,t;
int q1[N],q2[M],q3[M];
int hh1,tt1=-1,hh2,tt2=-1,hh3,tt3=-1;
int delta;
int get_max()
{
    int res=-1e9;
    if(hh1<=tt1) res=max(res,q1[hh1]);
    if(hh2<=tt2) res=max(res,q2[hh2]);
    if(hh3<=tt3) res=max(res,q3[hh3]);
    if(hh1<=tt1&&res==q1[hh1]) hh1++;
    else if(hh2<=tt2&&res==q2[hh2])   hh2++;
    else    hh3++;
    return res;
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        q1[++tt1]=x;
    }
    sort(q1,q1+n);
    reverse(q1,q1+n);
    for(int i=1;i<=m;i++)
    {
        int x=get_max()+delta;
        int left=x*1ll*u/v;
        int right=x-left;
        delta+=q;
        left-=delta;
        right-=delta; 
        q2[++tt2]=left;
        q3[++tt3]=right;
        if(i%t==0)  cout<<x<<' '; 
    }
    cout<<endl;
    for(int i=1;i<=n+m;i++)
    {
        int x=get_max();
        if(i%t==0)
        cout<<x+delta<<' ';
    }
    cout<<endl;
    return 0;
}