- C++
蚯蚓
- @ 2025-10-20 8:44:48
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int dat[N],val[N],sz[N],son[N][2],tag[N],n,m,q,u,v,t,idx,rt;
void up(int p){sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;}
void down(int p){
if(!tag[p])return ;
val[son[p][0]]+=tag[p];
val[son[p][1]]+=tag[p];
tag[son[p][0]]+=tag[p];
tag[son[p][1]]+=tag[p];
tag[p]=0;
}
void split(int p,int x,int &l,int &r){
if(!p){
l=r=0;
return ;
}
down(p);
if(val[p]<=x){
l=p;
split(son[p][1],x,son[p][1],r);
}
else{
r=p;
split(son[p][0],x,l,son[p][0]);
}
up(p);
}
int merge(int l,int r){
if(!l||!r)return l+r;
if(dat[l]>dat[r]){
down(l);
son[l][1]=merge(son[l][1],r);
up(l);
return l;
}
else{
down(r);
son[r][0]=merge(l,son[r][0]);
up(r);
return r;
}
}
void insert(int x){
int l,r;
split(rt,x,l,r);
dat[++idx]=rand();
val[idx]=x;
sz[idx]=1;
rt=merge(merge(l,idx),r);
}
void remove(int x){
int l,p,r;
split(rt,x,l,r);
split(l,x-1,l,p);
p=merge(son[p][0],son[p][1]);
rt=merge(merge(l,p),r);
}
int kthm(int p,int x){
down(p);
if(sz[son[p][1]]>=x)return kthm(son[p][1],x);
if(sz[son[p][1]]+1==x)return val[p];
return kthm(son[p][0],x-sz[son[p][1]]-1);
}
void inorder(int p){
if(!p)return ;
down(p);
inorder(son[p][0]);
cout<<val[p]<<" ";
inorder(son[p][1]);
}
signed main(){
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;i<=n;i++){
int x;
cin>>x;
insert(x);
}
for(int i=1;i<=m;i++){
int minn=kthm(rt,1);
remove(minn);
tag[rt]+=q;
val[rt]+=q;
int l=minn*u/v;
int r=minn-l;
insert(l);
insert(r);
if(i%t==0){
cout<<minn<<" ";
}
}
cout<<"\n";
for(int i=1;i<=n+m;i++){
if(i%t==0)cout<<kthm(rt,i)<<' ';
}
return 0;
}
0 条评论
目前还没有评论...