https://molmin.github.io/OI/problem/al0slh/solution

算法一：优先队列（$\Theta(m\log m)$）

首先，容易想到在 $q=0$ 时，我们只需要使用优先队列，每次取出最大的进行分割再放回去即可。

那么当 $q > 0$ 时，考虑怎么处理每次所有蚯蚓共同增加的长度 $q$。我们不可能每次都取出所有元素再一个一个地进行处理。所以我们考虑维护一个偏移量，表示整个集合要共同增加的量，每次取出时先求出原值再操作，然后减去偏移量放回即可。

时间复杂度 $\Theta(m\log m)$。

算法二：普通队列（$\Theta(m)$）

本题中我们还有更加优秀的 $\Theta(m)$ 的做法。

首先考虑 $q=0$ 的情形。这里作出 $p=\dfrac 12$ 时 $\left\lfloor px\right\rfloor$ 和 $x-\left\lfloor px\right\rfloor$ 的图像，会发现它们都是 单调不降 的。

要证：若 $x \leq y$，$0 < p < 1$，则 $\left\lfloor px\right\rfloor \leq \left\lfloor py\right\rfloor$ 且 $x-\left\lfloor px\right\rfloor \leq y-\left\lfloor py\right\rfloor$。

前一个结论易证，而对于后一个结论，易知

$$\begin{aligned} & p(y-x) \leq y-x \\ \Rightarrow \ & x-px \leq y-px \\ \Rightarrow \ & \left\lfloor x-px \right\rfloor \leq \left\lfloor y-px \right\rfloor. \\ \end{aligned} $$

注意到，$x,\ y$ 是整数，可得

$$x - \left\lfloor px \right\rfloor \leq y - \left\lfloor py \right\rfloor. $$

证毕。

参考文献：https://www.luogu.com.cn/paste/c4jthmhz（作者：dbxxx）

考虑维护三个队列 $Q,\ Q_1,\ Q_2$。

• 一开始将所有数按照 从大到小 的顺序加入队列 $Q$ 中。

• 每次从三个队列的队头中取最大的弹出，分割成 $\left\lfloor px \right\rfloor$ 和 $x - \left\lfloor px \right\rfloor$ 两段分别加入 $Q_1$ 和 $Q_2$ 的队尾。

• 易知每一步操作结束后三个队列的数都是 单调不增 的，得以保证下一次取出的必然是最大值。

再考虑 $q > 0$ 的情况。同样，我们还是维护一个偏移量，但是此时我们需要重新证明上面的结论。

要证：若 $x \leq y$，$0 < p < 1$，则 $\left\lfloor p(x+q)\right\rfloor \leq \left\lfloor py\right\rfloor +q$ 且 $x+q-\left\lfloor p(x+q)\right\rfloor \leq y-\left\lfloor py\right\rfloor+q$。

对于前一个结论，有

$$\left\lfloor p(x+q)\right\rfloor = \left\lfloor px+pq\right\rfloor \leq \left\lfloor py+q\right\rfloor = \left\lfloor py\right\rfloor +q. $$

对于后一个结论，根据 $q=0$ 时的结论，有

$$x+q-\left\lfloor p(x+q)\right\rfloor \leq x-\left\lfloor px\right\rfloor+q \leq y-\left\lfloor py\right\rfloor+q. $$

证毕。

时间复杂度 $\Theta(m)$。

// 2023.07.05

#include<bits/stdc++.h>
using namespace std;

queue<int> Q,Q1,Q2;
int n,m,q,u,v,t,a[100001];

void debug(int x){
    int n=Q.size();
    for(int i=1;i<=n;i++){
        int v=Q.front();
        printf("%lld ",v+1ll*x*q);
        Q.pop();Q.push(v);
    }
    printf("\n");
    n=Q1.size();
    for(int i=1;i<=n;i++){
        int v=Q1.front();
        printf("%lld ",v+1ll*x*q);
        Q1.pop();Q1.push(v);
    }
    printf("\n");
    n=Q2.size();
    for(int i=1;i<=n;i++){
        int v=Q2.front();
        printf("%lld ",v+1ll*x*q);
        Q2.pop();Q2.push(v);
    }
    printf("\n");
}

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--)
        Q.push(a[i]);
    for(int i=1;i<=m;i++){
        int maxlen=-2e9,from;
        if(!Q .empty()&&Q .front()>maxlen)maxlen=Q .front(),from=0;
        if(!Q1.empty()&&Q1.front()>maxlen)maxlen=Q1.front(),from=1;
        if(!Q2.empty()&&Q2.front()>maxlen)maxlen=Q2.front(),from=2;
        if(from==0)Q .pop();
        if(from==1)Q1.pop();
        if(from==2)Q2.pop();
        long long reallength=maxlen+(i-1ll)*q;
        if(!(i%t))printf("%lld ",reallength);
        Q1.push(int(reallength*u/v-(i-1ll)*q-q));
        Q2.push(int(reallength-reallength*u/v-(i-1ll)*q-q));
    }
    printf("\n");
    for(int i=1;i<=n+m;i++){
        int maxlen=-2e9,from;
        if(!Q .empty()&&Q .front()>maxlen)maxlen=Q .front(),from=0;
        if(!Q1.empty()&&Q1.front()>maxlen)maxlen=Q1.front(),from=1;
        if(!Q2.empty()&&Q2.front()>maxlen)maxlen=Q2.front(),from=2;
        if(from==0)Q .pop();
        if(from==1)Q1.pop();
        if(from==2)Q2.pop();
        long long reallength=maxlen+1ll*m*q;
        if(!(i%t))printf("%lld ",reallength);
    }
    printf("\n");
    return 0;
}

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;

bool cmp(const int &a,const int &b){
    return a>b;
}

priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/v;int tmp;
    for(t0=1;t0<=n;++t0)
        scanf("%d",&now[t0]);
    --t0;t1=t2=0;h=h1=h2=1;
    sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
    int top;
    for(int i=1;i<=m;++i){
        if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
        else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
        else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
        else top=cut2[h2],++h2;
        ;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
        top+=sigma;
        int a1=floor(p*(double)top),a2=top-a1;
        sigma+=q;
        a1-=sigma,a2-=sigma;
        cut1[++t1]=a1,cut2[++t2]=a2;
        if(i%t==0)printf("%d ",top);
    }
    putchar('\n');
    for(int i=h;i<=t0;++i)ans.push(now[i]);
    for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
    for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
    for(int i=1;ans.size();++i){
        if(i%t==0)printf("%d ",ans.top()+sigma);
        ans.pop();
    }
    return 0;
}