- 给定一个操作序列，包含 \((+,a_i),(\times,a_i)\) 两种操作。
- 初始 \(x=1\)，会从左到右依次执行所有操作得到一个终值 \(x'\)。
- 共有 \(lim\) 块钱，可以花 \(p1\) 块钱任意移动一个加法操作，或花 \(p2\) 块钱任意移动一个乘法操作。
- 求 \(x'\) 的最大值。
- \(1\le n\le10^6\)，保证初始的 \(x'\le2\times10^9\)
枚举乘法操作
首先去掉所有 \((*,1)\) 的操作，显然这些操作没有任何影响。
同时移动 \((+,a_i),(\times,a_i)\)，它们之间的影响比较复杂，不太能直接做。
考虑初始 \(x'\le2\times10^9\)，乘法操作数量其实非常小。因此我们尝试先枚举移动的乘法操作，然后再去移动加法操作。
注意到对于值相同的乘法操作，移动前面的若干个肯定优于移动后面的。
所以假设有 \(c_i\) 个值为 \(i\) 的乘法操作，枚举的复杂度应当是 \(\prod(c_i+1)\)。而 \(\prod i^{c_i}\le2\times10^9\)，这里的复杂度并不会很大。
处理加法操作
确定了乘法操作的移动后，移动每个加法操作的价值就能确定下来了。假设还能移动 \(k\) 个加法操作，则我们就是要求前 \(k\) 大的价值之和。
比赛时比较 sb，直接暴力 \(O(n)\) 做这个东西，T 飞了。
实际上，考虑乘法操作至多只有 \(\log V\) 个，而两个乘法操作之间的加法操作顺序是没有影响的，移动较大的肯定优于移动小的。
于是我们先二分第 \(k\) 大的价值，然后在每个段中二分求个数检验即可。
每次的复杂度应该是三只 \(\log\)。
代码
#include<bits/stdc++.h>
#define Cn const
#define CI Cn int&
#define N 1000000
#define LL long long
using namespace std;
namespace FastIO
{
#define FS 100000
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp void read(Ty& x) {x=0;while(!isdigit(oc=tc()));while(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts void read(Ty& x,Ar&... y) {read(x),read(y...);}
void readc(char& x) {while(isspace(x=tc()));}
}using namespace FastIO;
int n,c,lim,tot,p1,p2,s[N+5],v[N+5],h[N+5],dc,dv[N+5];vector<int> w[N+5],W[N+5],g[N+5];LL ans;
int f[N+5];void Calc(int k)//处理加法操作
{
int i,j,z,t=1;LL res=0;for(i=1;i<=c;++i) res+=1LL*s[i]*(tot/t),f[i]=(t-1)*(tot/t),!h[i]&&(t*=dv[v[i]]);//计算每段的权
LL r=0;for(i=1;i<=c;++i) !w[i].empty()&&(r=max(r,1LL*w[i].back()*f[i]));
LL l=0,u,tar;int ct,ll,rr,uu;while(l<r)//二分第k大值
{
for(u=l+r+1>>1,ct=0,i=1;i<=c;++i)//求个数检验
{
if(w[i].empty()||1LL*w[i].back()*f[i]<u) continue;tar=(u+f[i]-1)/f[i];
z=w[i].size(),ll=0,rr=z-1;while(ll^rr) w[i][uu=ll+rr-1>>1]>=tar?rr=uu:ll=uu+1;ct+=z-rr;//二分
}ct>=k?l=u:r=u-1;
}
for(ct=0,i=1;i<=c;++i)//求前k大之和
{
if(w[i].empty()||1LL*w[i].back()*f[i]<=l) continue;tar=l/f[i]+1;
z=w[i].size(),ll=0,rr=z-1;while(ll^rr) w[i][uu=ll+rr-1>>1]>=tar?rr=uu:ll=uu+1;ct+=z-rr,res+=1LL*W[i][rr]*f[i];//二分
}
ans=max(ans,res+(k-ct)*l);
}
void dfs(int x,int lim)//枚举乘法操作
{
if(x>dc) return Calc(lim/p1);dfs(x+1,lim);
for(vector<int>::iterator it=g[x].begin();it!=g[x].end()&&lim>=p2;++it) h[*it]=1,lim-=p2,dfs(x+1,lim);//对每种值移动前面的若干个
for(vector<int>::iterator it=g[x].begin();it!=g[x].end();++it) h[*it]=0;
}
int main()
{
int i,j,x,z;char op;read(n,lim,p1,p2);
for(c=tot=i=1;i<=n;++i) readc(op),read(x),op=='*'?x^1&&(v[c++]=x,tot*=x):(w[c].push_back(x),s[c]+=x);v[c]=1;//注意删去乘1的操作
for(i=1;i<=c;++i) for(sort(w[i].begin(),w[i].end()),z=w[i].size(),W[i]=w[i],j=z-2;j>=0;--j) W[i][j]+=W[i][j+1];
for(i=1;i<=c;++i) dv[i]=v[i];sort(dv+1,dv+c+1),dc=unique(dv+1,dv+c+1)-dv-1;
for(i=1;i<=c;++i) g[v[i]=lower_bound(dv+1,dv+dc+1,v[i])-dv].push_back(i);return dfs(2,lim),printf("%lld\n",ans+tot),0;
}