题解：CF1774F1 Magician and Pigs (Easy Version)

_2eyks · 2025-11-14 11:00:49 · 题解

这个玩意直接维护不好搞，考虑转化第三个操作。

如果没有 3 操作，肯定要动态维护前几个操作中，2 操作的总贡献 w。而对于一个 3 操作，剩余血量为 x 的猪猪将会分裂成两头猪猪，这两头猪猪的血量分别为 x,x-w，随后 w 变为原先的两倍。

我们考虑这样转化题意：对于每头猪，遇到 3 操作的时候可以选择是否将当前血量 -w，求使得这头猪猪血量 >0 的方案数，并对所有猪求方案数的和。

F1 好像可以直接平衡树维护，但我懒，不想写平衡树。而且平衡树没法做 F2。

令 V 为 x 值域的最大值，即 10^9。考虑到：

• 如果 3 操作的 w\geq V，则这个 3 操作无效。
• 如果 3 操作的 w=0，则把在这个 3 操作之前生成的所有猪猪，答案乘以 2。
• 反之，剩余情况的 3 操作只有 \log V 次，因为每次 3 操作会让 w 乘以 2。

那就直接暴力处理这 \log V 次第三种 3 操作就行。具体计算答案的时候，把这些 3 操作插入 vector，记录第 i 个三类 3 操作的 w 为 W_i，则 2W_i\leq W_{i+1}，问题可以类比拆二进制位来做。

时间复杂度 \Theta(n\log V)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=8e5+5,INF=1e9,M=998244353;
int n,op[N],val[N];
vector<int>e;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    int w=0,c=1,rs=0;
    fo(i,1,n){
        cin>>op[i];
        if (op[i]<3)
            cin>>val[i];
        if (op[i]==2)
            w=min(INF,w+val[i]);
        if (op[i]==3){
            val[i]=w;
            w=min(INF,w*2);
        }
    }
    w=0;
    ro(i,n,1){
        if (op[i]==1){
            int x=val[i]-w;
            if (x<=0)
                continue;
            int p=e.size();
            for (auto i:e){
                p--;
                if (x>i){
                    x-=i;
                    (rs+=(1ll<<p)*c%M)%=M;
                }
            }
            (rs+=c)%=M;
        }
        else if (op[i]==2)
            w=min(INF,w+val[i]);
        else{
            if (!val[i])
                c=c*2%M;
            else if (val[i]!=INF)
                e.push_back(val[i]);
        }
    }
    cout<<rs<<'\n';
    return 0;
}