本题中，我们将用符号 ⌊c⌋ \lfloor c \rfloor 表示对 c c 向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3 \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3 。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 n n 只蚯蚓（n n 为正整数）。每只蚯蚓拥有长度，我们设第 i i 只蚯蚓的长度为 ai a_i （i=1,2,…,n i = 1, 2, \ldots , n ），并保证所有的长度都是非负整数（即：可能存在长度为 0 0 的蚯蚓）。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p p （是满足 0<p<1 0 < p < 1 的有理数）决定，设这只蚯蚓长度为 x x ，神刀手会将其切成两只长度分别为 ⌊px⌋ \lfloor px \rfloor 和 x−⌊px⌋ x - \lfloor px \rfloor 的蚯蚓。特殊地，如果这两个数的其中一个等于 0 0 ，则这个长度为 0 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q q （是一个非负整常数）。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m m 秒才能到来 ……（m m 为非负整数）

蛐蛐国王希望知道这 m m 秒内的战况。具体来说，他希望知道：

  • m m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m m 个数）；
  • m m 秒后，所有蚯蚓的长度（有 n+m n + m 个数）。

蛐蛐国王当然知道怎么做啦！但是他想考考你 ……

链接

LYOI#103

题解

当 q=0 q = 0 时，首先将蚯蚓排序，然后每次将切割后的两段蚯蚓分别放入两个队列中，则三个队列始终是单调的。设第 i i 次取出并切开的蚯蚓的长度为 ai a_i ，切开之后两段的长度分别为 li l_i 和 ri r_i ，那么对于第 i+1 i + 1 取出的蚯蚓，一定有 ai+1<ai a_{i + 1} < a_i ，这是因为我们每次取最长的来切并且所有的蚯蚓长度只会减少，由此可得，一定有 li+1<li,ri+1<ri l_{i + 1} < l_i, r_{i + 1} < r_i 。

当 q≠0 q \neq 0 时，每秒钟除了被切的蚯蚓，其他所有蚯蚓长度增加 q q ，可以将其余蚯蚓增加 q q 改为被切开的两段减少 q q ，此时三个序列仍满足单调性，正确性显然。

时间复杂度为 O(nlogn+m) O(n\log n + m) ，如果被辣鸡stl中队列卡常，可以尝试手写队列。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
const int MAXN = 100000;
const int MAXM = 70000000;
queue<int> q[3];
int getMax () {
    int res = -1;
    for (int i = 0; i < 3; i++) if (!q[i].empty() && (res == -1 || q[i].front() > q[res].front())) res = i;
    return res;
}
bool cmp (int a, int b) { return a > b; }
int len[MAXN + 1];
int main () {
    freopen("earthworm.in", "r", stdin);
    freopen("earthworm.out", "w", stdout);
    int n, m, k, u, v, t;
    scanf("%d %d %d %d %d %d", &n, &m, &k, &u, &v, &t);
    for (int i = 0; i < n; i++) scanf("%d", &len[i]);
    sort(len, len + n, cmp);
    for (int i = 0; i < n; i++) q[0].push(len[i]);
    int d = 0, frt;
    for (int i = 1; i <= m; i++) {
        int j = getMax();
        frt = q[j].front();
        q[j].pop();
        frt += d;
        if (i % t == 0) printf("%d ", frt);
        int a = static_cast<long long>(frt) * u / v, b = frt - a;
        d += k;
        a -= d, b -= d;
        q[1].push(a); q[2].push(b);
    }
    printf("\n");
    for (int i = 1; i <= n + m; i++) {
        int j = getMax();
        int ans = q[j].front(); q[j].pop();
        ans += d;
        if (i % t == 0) printf("%d ", ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}