2024-10-27 19:49:02
发布于：浙江
30阅读
0回复
0点赞
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define long long long
struct modein{
modein operator >>(char &x){
x=getchar();
while(x!='+'&&x!='-'&&x!='*'&&x!='@')x=getchar();
return (modein){};
}
template<class T>
modein operator >>(T &x){
x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return (modein){};
}
}qin;
int n,m,k1,k2,c[1000010];
char mode[1000010];int v[1000010];
int ip[1000010];long res[1000010];
long mn[1000010],mx[1000010],to[1000010],ad[1000010],cs[1000010],mt[1000010];
void init(int p=1,int l=1,int r=n){
if(l==r){mn[p]=mx[p]=v[ip[l]],mt[p]=1,to[p]=-1;return;}
init(p<<1,l,(l+r)>>1),init(p<<1|1,((l+r)>>1)+1,r);
mn[p]=mn[p<<1],mx[p]=mx[p<<1|1],mt[p]=1,to[p]=-1;
}
void add(long w){mn[1]+=w,mx[1]+=w,ad[1]+=w;}
void mlt(long w){mn[1]*=w,mx[1]*=w,ad[1]*=w,cs[1]*=w,mt[1]*=w;}
void exd(long w){mn[1]+=w*v[ip[1]],mx[1]+=w*v[ip[n]],ad[1]+=w*v[ip[1]],cs[1]+=w;}
void down(int p,int l,int r){
if(to[p]!=-1){
mn[p<<1]=mx[p<<1]=to[p];
cs[p<<1]=ad[p<<1]=0;
to[p<<1]=to[p],mt[p<<1]=1;
mn[p<<1|1]=mx[p<<1|1]=to[p];
cs[p<<1|1]=ad[p<<1|1]=0;
to[p<<1|1]=to[p],mt[p<<1|1]=1;
to[p]=-1;
}
if(mt[p]!=1){
mn[p<<1]*=mt[p],mx[p<<1]*=mt[p];
mn[p<<1|1]*=mt[p],mx[p<<1|1]*=mt[p];
ad[p<<1]*=mt[p],cs[p<<1]*=mt[p];
ad[p<<1|1]*=mt[p],cs[p<<1|1]*=mt[p];
mt[p<<1]*=mt[p],mt[p<<1|1]*=mt[p];
mt[p]=1;
}
if(ad[p]){
mn[p<<1]+=ad[p],mn[p<<1|1]+=ad[p];
mx[p<<1]+=ad[p],mx[p<<1|1]+=ad[p];
ad[p<<1]+=ad[p],ad[p<<1|1]+=ad[p];
ad[p]=0;
}
if(cs[p]){
mn[p<<1|1]+=cs[p]*(v[ip[((l+r)>>1)+1]]-v[ip[l]]);
ad[p<<1|1]+=cs[p]*(v[ip[((l+r)>>1)+1]]-v[ip[l]]);
cs[p<<1]+=cs[p],cs[p<<1|1]+=cs[p];
mx[p<<1]+=cs[p]*(v[ip[(l+r)>>1]]-v[ip[l]]);
mx[p<<1|1]+=cs[p]*(v[ip[r]]-v[ip[l]]);
cs[p]=0;
}
}
void mnn(int p=1,int l=1,int r=n){
if(mx[p]<k2)return;
if(l==r){mn[p]=mx[p]=k2;return;}
down(p,l,r);
if(mx[p<<1]>=k2){
mnn(p<<1,l,(l+r)>>1);
mn[p<<1|1]=mx[p<<1|1]=k2;
cs[p<<1|1]=ad[p<<1|1]=0;
to[p<<1|1]=k2,mt[p<<1|1]=1;
}else mnn(p<<1|1,((l+r)>>1)+1,r);
mn[p]=mn[p<<1],mx[p]=mx[p<<1|1];
}
void mxx(int p=1,int l=1,int r=n){
if(mn[p]>k1)return;
if(l==r){mn[p]=mx[p]=k1;return;}
down(p,l,r);
if(mn[p<<1|1]<=k1){
mxx(p<<1|1,((l+r)>>1)+1,r);
mn[p<<1]=mx[p<<1]=k1;
cs[p<<1]=ad[p<<1]=0;
to[p<<1]=k1,mt[p<<1]=1;
}else mxx(p<<1,l,(l+r)>>1);
mn[p]=mn[p<<1],mx[p]=mx[p<<1|1];
}
long get(int k,int p=1,int l=1,int r=n){
if(l==r){return mx[p];}down(p,l,r);
if(k<=((l+r)>>1))return get(k,p<<1,l,(l+r)>>1);
return get(k,p<<1|1,((l+r)>>1)+1,r);
}
int main(){
qin>>m>>k1>>k2;
for(int i=1;i<=m;i++)qin>>mode[i]>>c[i];
qin>>n;for(int i=1;i<=n;i++)qin>>v[i],ip[i]=i;
sort(ip+1,ip+n+1,[](int a,int b){return v[a]<v[b];});
init();
for(int i=1;i<=m;i++){
if(mode[i]=='+')add(c[i]);
else if(mode[i]=='-')add(-c[i]);
else if(mode[i]=='*')mlt(c[i]);
else if(mode[i]=='@')exd(c[i]);
mnn(),mxx();
}
for(int i=1;i<=n;i++)res[ip[i]]=get(i);
for(int i=1;i<=n;i++)printf("%lld\n",res[i]);
return 0;
}
有帮助，赞一个