Description
本题中，我们将用符号⌊c⌋表示对c向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有n只蚯蚓（n为正整数)。每只蚯蚓拥有长度，我们设第i只蚯蚓的长度为ai(i=1,2,...,n)，并保证所有的长度都是非负整数（即:可能存在长度为0的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定，设这只蚯蚓长度为x，神刀手会将其切成两只长度分别为⌊px⌋和x−⌊px⌋的蚯蚓。特殊地，如果这两个数的其中一个等于0，则这个长度为0的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要m秒才能到来......
(m为非负整数）
蛐蛐国王希望知道这m秒内的战况。具体来说，他希望知道：
•m秒内，每一秒被切断的蚯蚓被切断前的长度（有m个数）
•m秒后，所有蚯蚓的长度（有n+m个数)。
先不谈正解，先看看暴力怎么搞，mlog(n+m)堆啊。
然而，据说有STL并不能得多少分，所以让我们学习一下手写heap吧2333
上浮，下沉。感觉蛮容易的，交了一下，70！！！
另外10分是由于u/v的数据在10^9，中间算的时候必须先开下longlong。水水80。开心
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct heap
{
int q[7200000];
int now;
heap() {now=0;}
void down(int x)
{
int goal;
while((x<<1|1)<=now&&(q[x]<q[x<<1]||q[x]<q[x<<1|1]))
{
goal=q[x<<1] > q[x<<1|1] ? x<<1 : x<<1|1;
swap(q[x],q[goal]);
x=goal;
}
if((x<<1)<=now&&q[x<<1]>q[x]) swap(q[x],q[x<<1]);
}
void up(int x)
{
while(x>1&&q[x]>q[x>>1])
swap(q[x],q[x>>1]),x>>=1;
}
void pop() {q[1]=q[now];now--;down(1);}
int top(){return q[1];}
void push(int x){q[++now]=x;up(now);}
bool empty(){return now==0;}
int size(){return now;}
}q;
int n,m,val,u,v,t,now,cnt;
int read()
{
int re=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int main()
{
n=read();m=read();val=read();u=read();v=read();t=read();
for(int i=1;i<=n;i++) q.push(read());
bool flag=1;
for(int i=1;i<=m;i++)
{
int tmp=q.top();
q.pop();
if(i%t==0)
{
if(flag) printf("%d",tmp+now),flag=0;
else printf(" %d",tmp+now);
}
tmp+=now;
now+=val;
int c=1ll*tmp*u/v;//记住数据范围。
q.push(c-now); q.push(tmp-c-now);
}
puts("");
flag=1;
while(!q.empty())
{
cnt++;
if(cnt%t==0)
{
if(flag) printf("%d",q.top()+now),flag=0;
else printf(" %d",q.top()+now);
}
q.pop();
}
puts("");
return 0;
}下面让我们聊一下正解。对于每次拿出来的蚯蚓,长度为i，切成两部分 i*u/v； i*(1-u/v).然后我们在拿出来一个蚯蚓，长度为j，显然 j-q<=i 然后我们分成了两部分 j*u/v ；j*(1-u/v)，然后我们发现先前切得部分变成了i*u/v+q；i*(1-u/v)+q；则i*u/v+q>(j-q)*u/v+q=j*u/v+q-q*u/v > j*u/v 所以每次切成的两段都是单调递减的，所以我们维护三个个队列，两个作为每次用来维护切成两段的单调队列，一个是原数组，每次找到队列们第一个元素最大的那个拿出来，分成两段后放到两个单调队列里。保证3个队列的首元素中有一个肯定是最优解。（谁出的题？？好机智）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int tmp,now,c,goal;
int n,m,q,u,v,t;
int que[3][7200000];
int head[3],tail[3];
int read()
{
int re=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
bool cmp(int x,int y)
{
return x>y;
}
void doit()
{
int tmp=-1<<30;
if(tail[1]>=head[1]&&tmp<que[1][head[1]]) goal=1,tmp=que[1][head[1]];
if(tail[2]>=head[2]&&tmp<que[2][head[2]]) goal=2,tmp=que[2][head[2]];
if(tail[0]>=head[0]&&tmp<que[0][head[0]]) goal=0;
}
int main()
{
n=read();m=read();q=read();u=read();v=read();t=read();
for(int i=1;i<=n;i++)
scanf("%d",&que[0][i]);
sort(que[0]+1,que[0]+n+1,cmp);
head[0]=1,tail[0]=n;
head[1]=head[2]=1;
bool flag=1;
for(int i=1;i<=m;i++)
{
doit();
tmp=que[goal][head[goal]];
head[goal]++;
tmp+=now;
if(!(i%t))
{
if(flag) printf("%d",tmp),flag=0;
else printf(" %d",tmp);
}
now+=q;
c=1ll*tmp*u/v;
que[1][++tail[1]]=c-now;
que[2][++tail[2]]=tmp-c-now;
}
puts("");
flag=1;
for(int i=1;i<=n+m;i++)
{
doit();
if(!(i%t))
{
if(flag) printf("%d",que[goal][head[goal]]+now),flag=0;
else printf(" %d",que[goal][head[goal]]+now);
}
head[goal]++;
}
puts("");
return 0;
}