Magician and Pigs
分析一下三个操作分别干了些什么
- 新添一只猪
- 使血量为 \(x\) 的猪血量变为 \(\max(x-v,0)\)
- 设前面操作后猪总共会受到 \(s\) 的伤害，复制一只血量为 \(\max(x-s,0)\) 的猪，使 \(s=s\times 2\)
根据操作 \(3\) 可得最多 \(\log x\) 次操作后会杀死任何一只复制的猪，此时复制变得没有任何意义。当没有任何操作 \(2\) 时，操作 \(3\) 变成了使猪的数量翻倍。所以考虑倒着做，处理每只猪最后能剩下多少猪。
预处理出每次操作 \(2/3\) 会造成多少伤害，对于操作 \(1\)，若它后面产生的伤害已经超过这只猪的血量，显然不会有任何贡献。先去掉操作 \(2\) 造成的伤害，再考虑操作 \(3\) 造成的伤害。如果倒过来的第 \(i\) 次操作 \(3\) 造成 \(x\) 伤害能吃下来，那么前面所有伤害之后都能吃下来，因为每次伤害至少翻倍，那一只猪会变为 \(2^{cnt-i}\) 只猪，\(cnt\) 表示这次操作 \(1\) 后面共有 \(cnt\) 次操作 \(3\)。这是没有复制的猪承受伤害能增加的数量，还有复制出来的猪承受伤害能增加的数量，所以将血量减去 \(x\)，再往前找。因为最多找 \(log x\) 次，所以复杂度为 \(O(n\log x)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=8e5+10,mx=1e9,mod=998244353;
int n,m,opt[N],val[N],c[N],cnt,s[N],d[N],tot,sum,res=1,ans;
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(opt[i]);
if(opt[i]!=3){
read(val[i]);
}
if(opt[i]==2){
sum+=val[i];
}
if(opt[i]==3){
val[i]=sum;
sum*=2;
}
sum=min(sum,mx);
}
sum=0;
for(int i=n;i;i--){
if(opt[i]==2){
sum+=val[i];
}
if(opt[i]==3){
if(val[i]==mx){
continue;
}
if(!val[i]){
res=res*2%mod;
continue;
}
c[++cnt]=val[i];
}
else{
val[i]-=sum;
if(val[i]<=0){
continue;
}
int S=0;
for(int j=1;j<=cnt;j++){
if(val[i]>c[j]){
S=(S+(1ll<<(cnt-j))%mod)%mod;
val[i]-=c[j];
}
}
ans=(ans+(S+1)*res)%mod;
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}