Description：

有 $n$ 只蚯蚓， $m$ 个时刻中每个时刻在所有蚯蚓中选一条最长的切成长为 $\lfloor len\times p\rfloor$ 和 $\lfloor len-len\times p\rfloor$ 的蚯蚓， $p$ 是给定浮点数，与此同时其他蚯蚓长长 $q$ ，问每时刻蚯蚓长度和最终所有蚯蚓长度。

$1\le n \le 10^5,1\le m \le 7\times 10^6$

Solution：

暴力用堆模拟 $+$ 卡常能得到 $85$ ，从数据范围来看正解应该是 $O(n)$ 的，也就是说必须 $O(1)$ 获得最长的蚯蚓，也就是说不能每次在所有蚯蚓中找最长的，必须观察题目性质来排掉一些可能性，于是可以发现这道题先切的蚯蚓产生的小蚯蚓一定比后切的产生的小蚯蚓长，因为他们都长长了相同的时间下先切的本来就长，所以原来就先切的后来还要先切，这启示我们可以用队列这个先进先出的数据结构来维护所有蚯蚓，于是这道题的做法就是维护三个队列，每次从三个队头中选出最长的切成两半，这里找最长一定要用 $\ge$ ，然后再把产生的两个新蚯蚓分别放入后两个队列，也就是说第一个队列只取出不加入，注意由于要满足单调性所以蚯蚓放入的队列不能颠倒。还有一个问题就是怎么处理长长，由于长长操作不会影响相互顺序，可以维护一个变量 $sigma$ 表示所有蚯蚓实际的长度都是当前队列中的长度 $+sigma$ ，每次操作时把取出的蚯蚓 $+sigma$ 再切，再把 $sigma+q$ ，再把操作的蚯蚓 $-sigma$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,q,u,v,w;

#define MAXN 7000010

int now[MAXN * 3],cut1[MAXN],cut2[MAXN];

bool cmp(int x,int y){return x > y;}

int h1,h2,h,t1,t2,t;

int main()

{

	scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&w);

	for(int i = 1;i <= n;++i)scanf("%d",&now[i]);

	t = n;t1 = t2 = 0;h1 = h2 = h = 1;

	sort(now + 1,now + 1 + n,cmp);

	int cur;

    int sigma = 0;

	for(int i = 1;i <= m;++i)

	{

		if(h > t)

		{

			if(cut1[h1] > cut2[h2])cur = cut1[h1++];

            else cur = cut2[h2++];

		}

        else

        {

            if(now[h] >= cut1[h1] && now[h] >= cut2[h2])cur = now[h++];

            else if(cut1[h1] >= now[h] && cut1[h1] >= cut2[h2])cur = cut1[h1++];

            else cur = cut2[h2++];

        }

        cur += sigma;

        if(i % w == 0)printf("%d ",cur);

        int a1 = floor((double)cur * (double)u / (double)v);

        int a2 = cur - a1;

        sigma += q;

        a1 -= sigma;a2 -= sigma;

        cut1[++t1] = a1;

        cut2[++t2] = a2;

	}

    puts("");

	for(int i = h1;i <= t1;++i)now[++t] = cut1[i];

    for(int i = h2;i <= t2;++i)now[++t] = cut2[i];

    sort(now + h,now + 1 + t,cmp);

    for(int i = 1;i <= t - h + 1;++i)if(i % w == 0)printf("%d ",now[h + i - 1] + sigma);

    puts("");

	return 0;

}