题目链接

  题目很长，题意如下：一开始有n个值，，有m次操作，每次操作选择一个最大的值x，将它分解成两个数，分别为，以及，然后，经过这个操作之后，对除了这两个数以外的其他数字进行 +q 操作。最后两行输出，第一行输出，是每次操作执行之前，我们找到的那个最大的值是多少；第二行输出，是我们执行完m次操作，现在这n+m个值都各自变成了几？

  由于输入的量加上操作的量很大，所以我们不能使用带有复杂度的大根堆来解决这个问题，这无疑是加大了我们这道问题的难度！

  那么，这暗示着我们需要寻找其中的“线性关系”了。

  我们会发现，我们取出来的值一定是排除“增量q”情况下的递减的。但，我们再想一下，同样经过T次“增量q”，如果先分解的两个，是不是后期分得的“增量q”会更多呢（因为分解成了两个，相当于每个都享受到了这样的优惠，但是没分解的，现在是两个共享同一个“增量q”），先分解的在随着时间的推移反而会越来越有优势。

  所以，我们不妨维护三个队列：

队列1:原本的值，按照从大到小排序；

队列2:分解之后，值偏大的那个，那么值越大的一定就先分解了，享受“增量q”福利肯定也更早；

队列3:分解之后，值偏小的那个，作用同上。

  那么，又如何维护“增量q”呢，实际上，我们只需要再多统计一个信息就可以了，就是这个值是第几轮生成的，用当前轮次减去生成的轮次，不就得到了它需要被增加多少次了呢。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int n, m, q, t;
ll u, v;
ll a[maxn];
struct node {ll val, id;node(ll a = 0, ll b = 0):val(a), id(b) {}friend bool operator < (node e1, node e2) {return e1.val - e1.id * q < e2.val - e2.id * q;}ll F(ll i) { return val + (i - id) * q; }
};
struct Heap {queue<node> Q[3];void clear() {for(int i = 0; i < 3; i ++) while(!Q[i].empty()) Q[i].pop();}bool empty() { return Q[0].empty() && Q[1].empty() && Q[2].empty(); }node Top() {node ans;int qid = -1;for(int i = 0; i < 3; i ++) {if(Q[i].empty()) continue;if(~qid) {if(Q[qid].front() < Q[i].front()) qid = i;}else qid = i;}ans = Q[qid].front();Q[qid].pop();return ans;}
} que;
int main() {scanf("%d%d%d%lld%lld%d", &n, &m, &q, &u, &v, &t);for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);sort(a + 1, a + n + 1, greater<ll>() );que.clear();for(int i = 1; i <= n; i ++) que.Q[0].push(node(a[i], 0));int tot = m / t;if(!tot) printf("\n");for(int i = 0; i < m; i ++) {node now = que.Top();if((i + 1) % t == 0) {tot --;printf("%lld%c", now.F(i), tot ? ' ' : '\n');}ll x = now.F(i) * u / v, y = now.F(i) - x;if(x < y) swap(x, y);que.Q[1].push(node(x, i + 1));que.Q[2].push(node(y, i + 1));}tot = (n + m) / t;if(!tot) printf("\n");for(int i = 1; i <= n + m; i ++) {node now = que.Top();if(i % t == 0) {tot --;printf("%lld%c", now.F(m), tot ? ' ' : '\n');}}return 0;
}