洛谷-P2827 蚯蚓（单调队列+延迟修改）¶

洛谷-P2827 蚯蚓（单调队列+延迟修改）¶

题目描述¶

本题中，我们将用符号 $[c]$ 表示对 c 向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有 n 只蚯蚓（n 为正整数）。每只蚯蚓拥有长度，我们设第 i 只蚯蚓的长度为 $a_i(i = 1,2,\cdots , n)$ ，并保证所有的长度都是**非负**整数（即：可能存在长度为 0 的蚯蚓）。每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p（是满足 0 < p < 1 的有理数）决定，设这只蚯蚓长度为 x，神刀手会将其切成两只长度分别为 $[px], x - [px]$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 0，则这个长度为 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q（是一个非负整常数）。蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来 ……（m 为非负整数）蛐蛐国王希望知道这 m 秒内的战况。具体来说，他希望知道：

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

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

输入格式¶

第一行包含六个整数 $n，m，q，u，v，t$ ，其中： $n，m，q$ 的意义见「题目描述」； $u，v，t$ 均为正整数，你需要自己计算 $p = \frac{u}{v}$ （保证$ 0 < u < v $）；$ t$ 是输出参数，其含义将会在「输出描述」中解释。第二行包含 n 个非负整数，为 $a_1, a_2, \cdots , a_n$ ，即初始时 n 只蚯蚓的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。保证 $1 \leq n \leq 10^5 , 0 \leq m \leq 7 \times 10^6, 0 < u < v \leq 10^9, 0 \leq q\leq 200, 1 \leq t \leq 71, 0 \leq a_i \leq 10^8$ 。

输出格式¶

第一行输出 $\left[ \frac{m}{t}\right]$ 个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒 …… 被切断蚯蚓（在被切断前）的长度。第二行输出 $\left[ \frac{m + n}{t}\right]$ 个整数，输出 m 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 t，第 2t，第 3t …… 的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。请阅读样例来更好地理解这个格式。

输入输出样例¶

输入 #1

3 7 1 1 3 1
3 3 2

输出 #1

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

输入 #2

3 7 1 1 3 2
3 3 2

输出 #2

4 4 5
6 5 4 3 2

输入 #3

3 7 1 1 3 9
3 3 2

输出 #3

//空行
2

说明/提示¶

【样例解释1】

在神刀手到来前：3 只蚯蚓的长度为 3, 3, 2。 1 秒后：一只长度为 3 的蚯蚓被切成了两只长度分别为 1 和 2 的蚯蚓，其余蚯蚓的长度增加了 1。最终 4 只蚯蚓的长度分别为 (1, 2), 4, 3。括号表示这个位置刚刚有一只蚯蚓被切断； 2 秒后：一只长度为 4 的蚯蚓被切成了 1 和 3。5 只蚯蚓的长度分别为：2, 3, (1, 3), 4； 3 秒后：一只长度为 4 的蚯蚓被切断。6 只蚯蚓的长度分别为：3, 4, 2, 4, (1, 3)； 4 秒后：一只长度为 4 的蚯蚓被切断。7 只蚯蚓的长度分别为：4, (1, 3), 3, 5, 2, 4； 5 秒后：一只长度为 5 的蚯蚓被切断。8 只蚯蚓的长度分别为：5, 2, 4, 4, (1, 4), 3, 5； 6 秒后：一只长度为 5 的蚯蚓被切断。9 只蚯蚓的长度分别为：(1, 4), 3, 5, 5, 2, 5, 4, 6； 7 秒后：一只长度为 6 的蚯蚓被切断。10 只蚯蚓的长度分别为：2, 5, 4, 6, 6, 3, 6, 5, (2, 4)。所以，7 秒内被切断的蚯蚓的长度依次为 3, 4, 4, 4, 5, 5, 6。7 秒后，所有蚯蚓长度从大到小排序为 6, 6, 6, 5, 5, 4, 4, 3, 2, 2。

【样例解释2】

这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。

虽然第一行最后有一个6没有被输出，但是第二行仍然要重新从第二个数再开始输出。

【样例解释3】

这个数据中只有t=9与上个数据不同。

注意第一行没有数要输出，但也要输出一个空行。

【数据范围】

#include <bits/stdc++.h>

using namespace std;

long long n, m, q, u, v, t;
double p;
vector<long long> seq(7e6 + 5);
queue<long long> q1, q2, q3; //三个单调队列

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

void solve()
{
    for (int i = 1; i <= m; ++i) {
        long long maxVal = LLONG_MIN;
        int flag = 0;
        if (!q1.empty() && q1.front() > maxVal) { maxVal = q1.front(); flag = 1; }
        if (!q2.empty() && q2.front() > maxVal) { maxVal = q2.front(); flag = 2; }
        if (!q3.empty() && q3.front() > maxVal) { maxVal = q3.front(); flag = 3; }

        switch(flag) {
            case 1: q1.pop(); break;
            case 2: q2.pop(); break;
            default: q3.pop();
        }

        long long delta = (i - 1) * q;
        maxVal += delta;
        q2.push(floor(maxVal * p) - delta - q);
        q3.push(maxVal - floor(maxVal * p) - delta - q);
        if (i % t == 0) cout << maxVal << ' ';
    }
    cout << endl;

    int cnt = 1;
    long long delta = m * q;
    while (true) {
        long long maxVal = LLONG_MIN;
        int flag = 0;
        if (!q1.empty() && q1.front() > maxVal) { maxVal = q1.front(); flag = 1; }
        if (!q2.empty() && q2.front() > maxVal) { maxVal = q2.front(); flag = 2; }
        if (!q3.empty() && q3.front() > maxVal) { maxVal = q3.front(); flag = 3; }

        if (!flag) break; //所有队列为空

        switch(flag) {
            case 1: q1.pop(); break;
            case 2: q2.pop(); break;
            default: q3.pop();
        }

        if (cnt++ % t == 0) cout << (maxVal + delta) << ' ';
    }
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> q >> u >> v >> t;
    p = u * 1.0 / v;

    for (int i = 0; i < n; ++i) cin >> seq[i];
    sort(seq.begin(), seq.begin() + n, cmp);
    for (int i = 0; i < n; ++i) q1.push(seq[i]);

    solve();

    return 0;
}

这道题目非常类似于P6033 合并果子加强版，重点在于挖掘题目中隐含的单调信息，从而优化程序。

这道题很容易联想到使用优先级队列，一个难点是如何去描述每过一秒，余下的蚯蚓长度增加 $q$ 。不妨假设 $q = 0$ ，那么就可以使用优先级队列，每次取出最大值，切割完成后重新加回到堆里面。如果 $q \neq 0$ ，类似于线段树或数列分块里的加法标记，我们可以考虑除了最大的长度需要切割以外，其余的都要增加 $q$ ，如果把最长的切割成 $[px]$ 和 $x - [px]$ 后，两个数据都减去 $q$ ，那么就相当于所有数据增加 $q$ 就得到了原始数据。时间复杂度 $O(m\log n)$ ，会超时。

假设有两条蚯蚓的长度分别为 $a, b, a > b$ ，当 $a$ 被切割成 $a_1 = [pa], a_2 = a - [pa]$ 两段，经过 $t$ 秒后，两段长度为 $a_1 + t\times q, a2 + t \times q$ ，此时切割 $b$ ，那么两段长度为 $b1 = [p(b + t \times q)], b_2 = b - [p(b + t\times q)]$ ，发现 $$ a_1 = [pa]+t \times q \geq b_1 = [p(b + t \times q)] $$ 另外一段也满足这个规律，因为 $t$ 的任意性，我们知道如果一条蚯蚓长度大于另一条，那么两段都切割完成后，对应的段也满足降序的关系。这也就意味着我们可以用三个队列，一个队列存储原始的数据，数据要先降序排列，另外两个队列，其中一个保存 $[px]$ 的部分，另一个保存剩余的部分，并且知道每个队列都具备单调性，所以每次选取最大值只需要从三个队列的头部元素选取即可。

分析时间复杂度：排序时间复杂度 $O(n \log n)$ ，对 $m$ 秒的模拟，时间复杂度 $O(m)$ ，将 $m +n$ 个数据输出，时间复杂度 $O(m +n)$ ，因为 $m$ 的数据范围比 $n$ 高一个量级，所以程序的时间复杂度是 $O(m + n \log n)$ 。