题意：

$简化题意就是给定n个数的序列，进行m次操作，每次操作为：$
$① \quad 从序列当中拿出一个最大的数x，如果有多个数最大，取其中任意一个；$
$②\quad 没有被拿出来的数全部加上q；$
$③\quad 将\lfloor x*p \rfloor和x - \lfloor x*p \rfloor重新放进序列；$
$然后问这m次操作每次拿出来的数是什么和操作完成后的序列降序后是什么$
$t是一个输出参数，就是不需要全部输出，每t个输出就行$

思路：

$如果直接用优先队列模拟需要O(mlogm),其中m上限为7e6，并不能通过$
$需要发掘这题的一个重要性质：$
$首先将原序列排好序，成降序：x_1 >= x_2 >= x_3>=.....>=x_n$
$第一步肯定是切x_1,将其切成l_1 = \lfloor x_1*p \rfloor和r_1 = x_1 - \lfloor x_1*p \rfloor$
$如果之后x_2要被切，也会被切成l_2 = \lfloor x_2*p \rfloor和r_2 = x_2 - \lfloor x_2*p \rfloor$
$这个性质就是：如果要切l_2那么一定会先切l_1,还有如果要切r_2一定会先切r_1$

$证明：$

$●\quad要切l_2，必先切l_1$
$① \quad l_1>=x_2，那么l_1一定早于x_2被切掉，更不用说l_2了$
$②\quad l_1 < x_2，那么下一步可能会切r_1，但x_2一定早于l_1被切，假设过了k秒x_2被切了$
$那么l_2 = \lfloor p*(x_2 + k\cdot q) \rfloor，这个时候因为l_1一直没有被切，所以也一直增长着$
$l_1 = \lfloor x_1*p \rfloor + k\cdot q，令k\cdot q = C \ 得l_1 = \lfloor x_1*p \rfloor + C,l_2 = \lfloor p*(x_2 + C) \rfloor$
$因为C是整数，而且是相加是可以放进去，所以l_1 = \lfloor x_1*p +C\rfloor = \lfloor p*(x_1+C)+(1-p)*C\rfloor$
$因为x_1 >= x_2，(1-p)*C这个东西是一个大于等于0的数，所以可以推出l_1 >= l_2$
$所以可以推出要切l_2必先切l_1$

$●\quad要切r_2，必先切r_1$
$①\quad r_2 >= x_2，那么r_2一定早于x_2被切掉，更不用说r_2了$
$②\quad r_2 < x_2，与上面相同的处理可得$
$r_1 = x_1 - \lfloor p*x_1 \rfloor+C，r_2 = x_2 + C - \lfloor p*(x_2+C) \rfloor$
$作差r_1 - r_2 = x_1 - x_2 + \lfloor p*(x_2+C) \rfloor - \lfloor p*x_1 \rfloor$
$d = x_1 - x_2 + \lfloor p*(x_2+C) \rfloor - \lfloor p*x_1 \rfloor放缩一下$
$d >= x_1 - x_2 + \lfloor p*x_2 \rfloor + \lfloor p*C \rfloor - \lfloor p*x_1 \rfloor$
$其中x_1 - x_2 + \lfloor p*x_2 \rfloor + - \lfloor p*x_1 \rfloor这个东西应该是大于等于0的$
$而 \lfloor p*C \rfloor 也是大于等于0的，所以d>=0$
$所以可以推出要切r_2必先切r_1$

$有了这个性质，就可以用三个队列O(1)地去维护最大值，q_1一开始为降序排序的x_i，$
$队首是一个max\{x_i\}，q_2和q_3都是空的，然后不断从三个队列的队首拿出一个最大值来切，$
$切完左段直接放入q_2的队尾，右段直接放入q_3的队尾，这是因为那条性质$
$切完第一刀，q_2里面只有l_1，q_3里面只有r_1，后面如果要切x_2产生了l_2，r_2$
$也一定保证在l_1，r_2后面被切掉了,因为l_1，r_1比他们早进队$

$最后模拟的时候，注意因为每次都会加上一个q，可以手写一个queue$
$里面存放一个属性tag作为偏移量表示该队列整个加上一个tag，$
$每次操作时，每个队列的tag都加上tag，$
$那么取元素的时候注意加上一个tag，加元素的时候注意减去一个tag$

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n,m,q,u,v,t;
double p;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct que {
    int tag = 0;
    int a[7500005], l, r;
    que(){l = r = 1;}
    bool empty() {return l == r;}
    void push(int x) {a[r] = x - tag;++r;}
    void add() {tag += q;}
    int front() { return a[l] + tag;}
    int pop() {++l; return a[l-1] + tag;}
}q1,q2,q3;
//取出三个队列队头的最大值，并弹出 
int getmx(){
    int mx = -0x3f3f3f3f;
    int flag = 0;
    if(!q1.empty() && mx < q1.front()) {mx = q1.front();flag = 1;}
    if(!q2.empty() && mx < q2.front()) {mx = q2.front();flag = 2;}
    if(!q3.empty() && mx < q3.front()) {mx = q3.front();flag = 3;}
    switch(flag){
        case 1 : q1.pop();break;
        case 2 : q2.pop();break;
        default : q3.pop();
    }
    return mx;
}

void cut(int x) {
    q1.add(),q2.add(),q3.add();
    q2.push(int(p*x));
    q3.push(x - int(p*x));
}
void solve(){
    for(int i = 1;i <= m;i++){
        int x = getmx();
        if(i%t == 0) printf("%d ",x);
        cut(x);
    }
    puts("");
}
int main(){
    n = read(),m = read(),q = read(),u = read(),v = read(),t = read();
    p = u * 1.0 / v;
    for(int i = 1;i <= n;i++) a[i] = read();
    sort(a + 1,a + 1 + n);
    for(int i = n;i >= 1;i--) q1.push(a[i]);
    solve();
    for(int i = 1;i <= n + m;i++){
        int x = getmx();
        if(i%t == 0) printf("%d ",x);
    }    
    return 0;
}

【每日一题】蚯蚓

题意：

思路：