题目传送门：https://www.luogu.org/problemnew/show/P2827
自测时被题面所误导…，题面中说逢t的倍数才输出答案，以为有什么玄妙的方法直接将m次操作变成了m/t次操作。结果GG….
65分做法：写一个左偏树，每次取出最顶端元素，对堆中其余元素全部+q（可以用标记完成），将该元素取出后，切为两段后再丢入该树中。时间复杂度为O((m+n) log m)。
幸好我不会65分的STL做法，据说此题有人用STL被卡了5分…..
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define M 1100000
using namespace std;
priority_queue<int> Q;
int n,m,q,t;
int tag[M]={},a[M]={},lc[M]={},rc[M]={}; void pushdown(int x){
if(!tag[x]) return;
tag[lc[x]]+=tag[x]; tag[rc[x]]+=tag[x];
a[lc[x]]+=tag[x]; a[rc[x]]+=tag[x];
tag[x]=;
}
int merge(int x,int y){
if(!x) return y;
if(!y) return x;
if(a[x]>a[y]){
pushdown(x);
rc[x]=merge(rc[x],y);
swap(lc[x],rc[x]);
return x;
}else{
pushdown(y);
lc[y]=merge(x,lc[y]);
swap(lc[y],rc[y]);
return y;
}
}
int rt=,use=;
long long v,u;
int main(){
freopen("earthworm.in","r",stdin);
freopen("earthworm.out","w",stdout);
cin>>n>>m>>q>>u>>v>>t;
for(int i=;i<=n;i++){
int x; scanf("%d",&x);
use++; a[use]=x;
rt=merge(use,rt);
}
for(int i=;i<=m;i++){
int x=a[rt],lastrt=rt;
rt=merge(lc[rt],rc[rt]);
tag[rt]+=q; a[rt]+=q;
if(i%t==) printf("%d ",x);
int x1=(u*x)/v,x2=x-x1;
lc[lastrt]=rc[lastrt]=; a[lastrt]=x1;
rt=merge(rt,lastrt);
use++; a[use]=x2;
rt=merge(use,rt);
}
printf("\n");
for(int i=;i<=m+n;i++){
int x=a[rt]; rt=merge(lc[rt],rc[rt]);
if(i%t==) printf("%d ",x);
}
printf("\n");
}
很垃圾的65分代码
下面说下100%的做法。
首先，先开三个队列，x,y,z。初始状态下，队列x中保存的是完全没有被切过的蚯蚓的长度（初始时排个序，最大的在最前面），队列y中保存一条被切开的蚯蚓前半部分的长度，队列z中保存一条被切开的蚯蚓的后半部分的长度。我们需保证y，z中元素的单调递减性。
不妨设q=0。由于p=[0,1]，则有x[1]≥y[1],z[1]。又因x[i]≥x[i-1],则有y[i]≥y[i-1]，z[i]≥z[i-1]。我们每次在x,y,z三个队列的头部取出长度最长的蚯蚓，随后将其分为两半后，分别直接加至y队列和z队列末尾，基于上述性质，无需排序或树结构维护y,z的单调性。
这种方法已经可以拿90分了…
实际上，当q≠0时，通过一些小的操作，y,z的单调性依然能够满足。
假设当前时间为t，若取出元素入队的时间为t0,入队时长度为x,则出队长度为q(t-t0)+x。我们修改下元素入队的规则，假设当前需要将x入队，则在x入队前，将x减去q*t0，再加入队列中。不难证明该方法可以保证y，z队列依然满足单调性。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define L long long
#include<queue>
#define INF 1231231231
#define M 10000010
using namespace std;
int x[M]={},y[M]={},z[M]={};int a[M]={},b[M]={};
int u,v,q,t,h1=,h2=,h3=,t1=,t2=,t3=; int n,m;
int main(){
freopen("earthworm.in","r",stdin);
freopen("earthworm.out","w",stdout);
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=;i<=n;i++) scanf("%d",a+i);
sort(a+,a+n+);
for(int i=n;i;i--) x[t1++]=a[i];
for(int i=,pls=;i<=m;i++){
int tmp=-INF,id=;
if(h1<t1) if(tmp<x[h1]) tmp=x[h1],id=;
if(h2<t2) if(tmp<y[h2]) tmp=y[h2],id=;
if(h3<t3) if(tmp<z[h3]) tmp=z[h3],id=;
tmp+=pls; pls+=q;
if(i%t==) printf("%d ",tmp);
if(id==) h1++; if(id==) h2++; if(id==) h3++;
L y1=((L)tmp*u)/v,z1=tmp-y1;
y[t2++]=(y1-pls); z[t3++]=(z1-pls);
}
int pls=(m)*q; printf("\n");
for(int i=;i<=n+m;i++){
int tmp=-INF,id=;
if(h1<t1) if(tmp<x[h1]) tmp=x[h1],id=;
if(h2<t2) if(tmp<y[h2]) tmp=y[h2],id=;
if(h3<t3) if(tmp<z[h3]) tmp=z[h3],id=;
tmp+=pls; if(i%t==) printf("%d ",tmp); //b[i]=tmp;
if(id==) h1++; if(id==) h2++; if(id==) h3++;
}
//for(int i=1;i<=n+m;i++) printf("%lld ",b[i]);
}
