【学习笔记】CF1774F2 Magician and Pigs (Hard Version)

首先不同的$1$操作之间是互不影响的，因此不妨考虑只有一个$1$操作的情形。对于相邻的$2$操作显然可以合并。然后对于一个$3$操作，可以看成是把之前的操作序列复制了一遍，那么相当于把原来的$x$序列复制一遍到最前面，然后对于后一半$x$序列全部减去$\delta$，并且$\delta$乘以$2$，因此$3$操作不会超过$\log$次。不难发现$x$序列具有单调性，那么我们可以在这个长度为$2^k(k\le \log n)$的序列中二分找到第一个$>0$的位置。观察发现我们只需求出操作完后队首元素的值即可，因为前后两半具有对称关系。复杂度$O(n\log n)$。细节：$\delta$的初值应该是之前展开过后所有$2$操作的和。$\delta =0$的情况需要特判。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define db double
using namespace std;
const int mod=998244353;
const int N=1e6+5;
int n,m,nxt[N],nxt2[N];
ll s[N],s2[N],c[N],f[N],res;
struct node{
	int op;
	ll x;
}a[N];
ll fpow(ll x,ll y){
	ll z(1);
	for(;y;y>>=1){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
	}return z;
}
int main(){
//	freopen("data.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].op,s[i]=s[i-1],s2[i]=s2[i-1];
		if(a[i].op==1||a[i].op==2)cin>>a[i].x;
		if(a[i].op==2)s[i]+=a[i].x;
		if(a[i].op==3)s2[i]++;
	}for(int i=n;i>=1;i--){
		if(a[i+1].op==3)nxt[i]=i+1;
		else nxt[i]=nxt[i+1];
		if(a[i+1].op==2)nxt2[i]=i+1;
		else nxt2[i]=nxt2[i+1];
	}
	for(int i=1;i<=n;i++){
		if(a[i].op==1){
			if(!f[0]){
				int j=nxt2[i];
				if(!j){
					res=(res+fpow(2,s2[n]-s2[i]))%mod;
					continue;
				} ll mul=fpow(2,s2[j]-s2[i]);
				m=0;
				for(j=nxt[j];j&&f[m]<=1e9;j=nxt[j]){
					m++,c[m]=s[j]-s[i],f[m]=((m==1)?f[m-1]:f[m-1]*2)+(c[m]-c[m-1]);
				}a[i].x-=s[n]-s[i];
				for(j=m;j>=1;j--){
					if(a[i].x-f[j]>0){
						res=(res+(1ll<<j-1)*mul%mod)%mod;
						a[i].x-=f[j];
					}
				}if(a[i].x>0) res=(res+mul)%mod;
			}
			else{
				m=0;
				for(int j=nxt[i];j&&f[m]<=1e9;j=nxt[j]){
					m++,c[m]=s[j]-s[i],f[m]=((m==1)?f[m-1]:f[m-1]*2)+(c[m]-c[m-1]);
				}assert(m<=31);a[i].x-=s[n]-s[i];
				for(int j=m;j>=1;j--){
					if(a[i].x-f[j]>0){
						res=(res+(1ll<<j-1))%mod;
						a[i].x-=f[j];
					}
				}if(a[i].x>0) res++;
			}
			
		}else if(a[i].op==2)f[0]+=a[i].x;
		else f[0]=min(1000000000ll,f[0]*2);
	}cout<<res;
}