题解

思路分析

这是一道经典的堆优化模拟问题，需要高效维护最大值并处理大规模数据。

问题建模

• 每秒选择最长的蚯蚓，长度为 $x$，切成 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 两段
• 其余蚯蚓长度增加 $q$
• 共切 $m$ 次，输出被切的蚯蚓长度和最终所有蚯蚓长度

核心思路

1. 单调性观察

关键发现：蚯蚓被切的时间越早，最终长度越大（因为每秒都会增长 $q$）。

具体来说：

• 初始蚯蚓按长度降序排列后，被切的顺序也是递减的
• 第 $i$ 秒切出的两段蚯蚓，都比第 $i+1$ 秒切出的蚯蚓长（因为被切时刻不同）

2. 三队列维护

利用单调性，维护三个队列：

• 队列0：初始蚯蚓（降序排列）
• 队列1：切出的较长段 $\lfloor px \rfloor$（按切割时间顺序）
• 队列2：切出的较短段 $x - \lfloor px \rfloor$（按切割时间顺序）

每次取最大值时，只需比较三个队列的队首元素。

3. 增量技巧（关键优化）

为避免每秒对所有蚯蚓 +q，使用差分思想：

• 用变量 add 记录累计增量（表示已经过了多少秒 $\times q$）
• 第 $i$ 秒：add = i \times q
• 切蚯蚓时：真实长度 = 队列中值 + add
• 新蚯蚓入队时：存储值 = 真实长度 - add - q

为什么要减 q？ 因为新蚯蚓是刚切出来的，在下一秒才开始增长，而队列中其他蚯蚓已经增长了这一秒。

例子：

• 第1秒：切出长度10的蚯蚓，分成 $6$ 和 $4$
• 此时 add = q
• 存储值：$6 - q - q = 6 - 2q$ 和 $4 - 2q$
• 第2秒取出时：$(6-2q) + 2q = 6$（正确！）

算法步骤

1. 初始化：

   • 将初始蚯蚓降序排序，放入队列1（用数组模拟）
   • 创建两个队列存放切出的蚯蚓

2. 模拟切割（$m$ 次）：

   • 比较三个队列队首，取最大值 $x$（加上累计增量 add）
   • 计算切成的两段：$a = \lfloor \frac{u \cdot x}{v} \rfloor$，$b = x - a$
   • 将 $a - add - q$ 和 $b - add - q$ 分别入队
   • 更新 add += q
   • 按需输出（每 $t$ 次输出一次）

3. 输出最终长度：

   • 依次从三个队列取出（每次取最大），加上 add 得到真实长度
   • 按需输出（每 $t$ 个输出一次）

复杂度分析

• 排序：$O(n \log n)$
• 模拟切割：$O(m)$
• 输出结果：$O(n + m)$
• 总时间复杂度：$O(n \log n + m)$
• 空间复杂度：$O(n + m)$

关键优化

• 使用数组模拟队列而非 STL priority_queue（避免堆操作的对数复杂度）
• 快速 I/O（使用 getchar()/putchar()）
• 差分思想避免每秒更新所有蚯蚓

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 7.1e6 + 7;
int pque[N], sz;
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while ((ch<'0') || (ch>'9')) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ((ch>='0') && (ch<='9')) {
        x = (x<<3) + (x<<1) + (ch-'0');
        ch = getchar();
    }
    return (f==1 ? x : -x);
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
        write(x/10);
    putchar(x%10 + '0');
}
void up(int u) {
    while (u>1 && pque[u]>pque[u>>1]) {
        swap(pque[u], pque[u>>1]);
        u >>= 1;
    }
}
void down(int u) {
    while (u+u <= sz) {
        int v = u+u;
        if (v+1<=sz && pque[v+1]>pque[v])
            ++v;
        if (pque[v] <= pque[u])
            return;
        swap(pque[v], pque[u]);
        u = v;
    }
}
void push(int x) {
    pque[++sz] = x;
    up(sz);
}
void pop() {
    if (sz == 1) {
        pque[1] = 0;
        sz = 0;
        return;
    }
    swap(pque[1], pque[sz]);
    --sz;
    down(1);
}
int main() {
    // freopen("data.txt", "r", stdin);
    int n, m, q, u, v, t, add = 0, tot = 0;
    n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        push(x);
    }
    while (m--) {
        int x = pque[1]+add; pop();
        if (++tot == t) {
            write(x);
            putchar(' ');
            tot = 0;
        }
        int a = 1LL*x*u/v; int b = x-a;
        push(a-add-q), push(b-add-q);
        add += q;
    }
    putchar('\n');
    tot = 0;
    while (sz) {
        int x = pque[1]+add; pop();
        if (++tot == t) {
            write(x);
            putchar(' ');
            tot = 0;
        }
    }
    return 0;
}
/*
n         10^5
m     7 * 10^6
t     71
a[i]      10^8
u, v      10^9
q     200
*/

题解

「蚯蚓」模拟的核心是维护当前长度的最大值，并把它按比例拆成两段。直接使用优先队列会超时，因此代码将三个来源的队列分离，并用指针和懒加值来维护：

1. 初始化：读入初始长度数组 a 并按降序排序。b、c 分别存放拆分后产生的两段。
2. 懒标记：由于每经过一次操作，所有蚯蚓都会统一加上 q，程序在取出最大值时临时加上 (i-1)*q，并在把新段放入 b、c 时再减去当前的增量，等到后续取出时补回即可。
3. 多路合并：用三个指针 $la,lb,lc$ 指向目前仍未取走的段，每次比较三者的真实长度（考虑懒加值）选出最大的那条蚯蚓。把长度 l 按比例拆成 l*u/v 和 l - l*u/v 两条，分别放进 b、c 的末尾。
4. 输出：每经过 t 次操作输出一次当前取出的长度；最后还要把所有剩余的段（包括 b、c 中的）按取出的顺序补齐输出，同样需要补上总共增加的 m*q。

由于每条蚯蚓最多被拆一次，整个过程只在数组上前移指针，时间复杂度 \(O((n+m)\ log(n+m))\)≈\(O(n+m)\)，可以满足数据范围。

#include<cstdio>
using namespace std;
long long n,m,q,u,v,t,a[200000],b[7100000],c[7100000],qq[200000],la,ra,lb,rb,lc,rc,i,l,aa,bb,p;
void sort(int l,int r)
{
	int i=l,j,k=l,mid=(l+r)/2;
	j=mid+1;
	if(l==r)
	{
		qq[l]=a[l];
		return;
	}
	sort(l,mid);
	sort(mid+1,r);
	while(i<=mid&&j<=r)
	{
		if(qq[i]>=qq[j])
		{
			a[k]=qq[i];
			i++;
		}
		else
		{
			a[k]=qq[j];
			j++;
		}
		k++;
	}
	while(i<=mid)
	{
		a[k]=qq[i];
		i++;
		k++;
	}
	while(j<=r)
	{
		a[k]=qq[j];
		j++;
		k++;
	}
	for(i=l;i<=r;i++)
	qq[i]=a[i];
}
main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
	la=1;
	ra=n;
	lb=1;
	lc=1;
	for(i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	sort(1,n);
	for(i=1;i<=m;i++)
	{
		l=-1000000000000;
		if(ra>=la&&a[la]>=l)
		{
			l=a[la];
			p=1;
		}
		if(rb>=lb&&b[lb]>=l)
		{
			l=b[lb];
			p=2;
		}
		if(rc>=lc&&c[lc]>=l)
		{
			l=c[lc];
			p=3;
		}
		l=l+(i-1)*q;
		aa=l*u/v;
		bb=l-aa;
		if(i%t==0)
		printf("%lld ",l);
		rb++;
		b[rb]=aa-i*q;
		rc++;
		c[rc]=bb-i*q;
		if(p==1)
		la++;
		if(p==2)
		lb++;
		if(p==3)
		lc++;
	}
	printf("\n");
	for(i=1;i<=n+m;i++)
	{
		l=-1000000000000;
		if(ra>=la&&a[la]>=l)
		{
			l=a[la];
			p=1;
		}
		if(rb>=lb&&b[lb]>=l)
		{
			l=b[lb];
			p=2;
		}
		if(rc>=lc&&c[lc]>=l)
		{
			l=c[lc];
			p=3;
		}
		l=l+m*q;
		if(i%t==0)
		printf("%lld ",l);
		if(p==1)
		la++;
		if(p==2)
		lb++;
		if(p==3)
		lc++;
	}
}