$蚯蚓$蚯蚓

题面见链接 .

$正解部分$正解部分

若直接使用优先队列暴力搞的话, 复杂度为 $O\left(Mlog\right(N+M\left)\right)$O(Mlog(N+M)), 其中 $M$M 为 $7\ast 10^6$7∗106 .
需要 $O\left(M\right)$O(M) 的时间复杂度才能 $AC$AC .

$设$设 蚯蚓 $x$x 的长度为 $le{n}_x$lenx​ 被切开后分为 $ple{n}_x,le{n}_x-ple{n}_x$plenx​,lenx​−plenx​ 两个蚯蚓,
蚯蚓 $y$y 的长度为 $le{n}_y$leny​ 被切开后分为 $ple{n}_y,le{n}_y-ple{n}_y$pleny​,leny​−pleny​ 两个蚯蚓, 且 $le{n}_y\&lt;le{n}_x$leny​<lenx​,

假如刚开始切 $x$x 得到 $ple{n}_x,(1-p)le{n}_x$plenx​,(1−p)lenx​, 然后切 $y$y, 得到 $p(le{n}_y+q),(1-p)(le{n}_y+q)$p(leny​+q),(1−p)(leny​+q),

此时切 $x$x 得到的两个蚯蚓长度分别为

• $ple{n}_x+q\&gt;p(le{n}_y+q)=ple{n}_y+pq$plenx​+q>p(leny​+q)=pleny​+pq
• $(1-p)le{n}_x+q\&gt;(1-p)(le{n}_y+q)=(1-p)le{n}_y+(1-p)q$(1−p)lenx​+q>(1−p)(leny​+q)=(1−p)leny​+(1−p)q

得到结论: 较长的蚯蚓先切得到的小蚯蚓 比 较短的蚯蚓后切得到的小蚯蚓 更长., 满足 单调性 .

于是开三个单调的队列, 第一个队列存储开始时排好序的蚯蚓, 第二个存切了之后第一条小蚯蚓, 第三个存第二条小蚯蚓,
每次取出三个队列中的最大队首, 然后 $O\left(1\right)$O(1) 处理即可 .

时间复杂度 $O\left(M\right)$O(M) .

$实现部分$实现部分

对长度增长的处理使用外部标记 $tag$tag, 每次取出元素 $x$x 后, 将 $x+=tag$x+=tag, 然后分裂成 $x_1,x_2$x1​,x2​, 推入队列时需要 $-=tag+q$−=tag+q, 然后 $tag+=q$tag+=q .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e7 + 5;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int N;
int M;
int q_;
int u_;
int v_;
int t_;
int A[maxn];

ll tag;
ll Ans[maxn];

int main(){
        scanf("%d%d%d%d%d%d", &N, &M, &q_, &u_, &v_, &t_);
        std::queue <ll> Q[3];
        for(reg int i = 1; i <= N; i ++) A[i] = read();
        std::sort(A+1, A+N+1);
        for(reg int i = N; i >= 1; i --) Q[0].push(A[i]);
        for(reg int i = 1; i <= M; i ++){
                int t = 0;
                if(Q[0].size()) t = 0;
                else if(Q[1].size()) t = 1;
                else t = 2;
                if(Q[0].size() && Q[0].front() > Q[t].front()) t = 0;
                if(Q[1].size() && Q[1].front() > Q[t].front()) t = 1;
                if(Q[2].size() && Q[2].front() > Q[t].front()) t = 2;
                Ans[i] = Q[t].front() + tag;
                ll tmp = Q[t].front() + tag; Q[t].pop();
                ll tmp_1 = 1ll*tmp*u_ / v_;
                ll tmp_2 = tmp - tmp_1;
                Q[1].push(tmp_1-tag-q_), Q[2].push(tmp_2-tag-q_);
                tag += q_;
        }
        for(reg int i = t_; i <= M; i += t_) printf("%lld ", Ans[i]);
        printf("\n");
        int cnt = 0;
        for(reg int i = 0; i <= 2; i ++) while(!Q[i].empty()){ Ans[++ cnt] = Q[i].front(); Q[i].pop(); }
        std::sort(Ans+1, Ans+cnt+1); std::reverse(Ans+1, Ans+cnt+1);
        for(reg int i = t_; i <= N+M; i += t_) printf("%lld ", Ans[i]+tag);
        return 0;
}