题面
题解
只考虑一方，每一个操作都可以写成 \(x\gets \max(0,\min(S,x+B_i))\) 的形式。
法一：
定义 “碰壁” 表示当前 \(x\gets \max(0,\min(S,x+B_i))\) 操作中对 \(0\) 取 \(\max\) 和对 \(S\) 取 \(\min\) 之一起了作用（即 \(x+B_i\) 超出了 \([0,S]\) 范围）。
在所有操作前插入一个 \(-\infty\) 操作和一个 \(X\) 操作，这样做的好处是：游戏一定是从 “先碰了一次下壁” 开始的。
考虑找出最后一次碰壁的时间 \(ed\) 以及它碰的是哪个壁，找出来之后就好做了。
我们将整个游戏的情形用下图的示意图表示：
上下两条黑线分别表示上下壁，红线是 \(x\) 随操作的变化形成的折线。也就是说，我们这么看游戏中的碰壁：先碰若干次下壁、再碰若干次上壁、再碰若干次下壁……。
我们把连续碰某一侧壁的部分称为 “一段”，一段中最后一次碰壁的位置称为这段的 “结尾”。我们发现，相邻两段的结尾之间一定存在两个点 \(i,j\) 使得 \(\left|\sum\limits_{k=i}^jB_k\right|>S\)。同时若存在 \(i,j\) 满足 \(\left|\sum\limits_{k=i}^jB_k\right|>S\) 那么 \(i\) 或之后一定会有碰壁。
这有助于我们定位最后一段的位置：找到 \(i\) 最大的 \(i,j\) 满足 \(\left|\sum\limits_{k=i}^jB_k\right|>S\)，那么最后一段一定在 \(i\) 之后而且 \(i\) 之后不存在其他段。
定位了最后一段之后怎么定位最后一次碰壁呢？由于 \(i\) 之后只会在同一侧碰壁，所以我们找到 \(i\) 之后 \(\left|\sum\limits_{k=i}^{ed}B_k\right|\) 最大的位置即为 \(ed\)。而且我们能通过 \(\left|\sum\limits_{k=i}^{ed}B_k\right|\) 的正负来判断碰的是哪一侧壁。
法二：
考虑分治，假设我们当前要解决 \(\operatorname{solve}(x,l,r)\)：进来的数是 \(x\)，经过操作 \(B_l,\cdots,B_r\) 后得到的是什么。
分两类讨论：
- 若 \([mid+1,r]\) 中存在 \(i,j\) 满足 \(\left|\sum\limits_{k=i}^jB_k\right|>S\)，那么在 \([mid+1,r]\) 中一定会碰壁，直接那么 \([l,mid]\) 操作就相当于没用了，直接进入 \(\operatorname{solve}(*,mid+1,r)\) 解决即可，其中 \(*\) 填什么并不重要。
- 若 \([mid+1,r]\) 中不存在 \(i,j\) 满足 \(\left|\sum\limits_{k=i}^jB_k\right|>S\)，此时并不代表着在 \([mid+1,r]\) 中一定不会碰壁，但可以说明在 \([mid+1,r]\) 中至多只会碰同一侧的壁，这跟上一题最后一部分是一样的。那么我们可以先求出 \(x\) 经过 \([l,mid]\) 会得到的数 \(x'=\operatorname{solve}(x,l,mid)\)，然后找到 \([mid+1,r]\) 中满足 \(\left|\sum\limits_{k=mid+1}^jB_k\right|\) 最大的位置 \(j\)，那么 \(j\) 就是 \([mid+1,r]\) 中最后一次碰壁的位置（当然需要先根据 \(x'+\sum\limits_{k=mid+1}^jB_k\) 判断有没有碰壁）。
法二代码：
#include<bits/stdc++.h>
#define N 500010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,q,X,Y,S;
ll sum[N<<2],maxn[N<<2],minn[N<<2];
void up(int k)
{
sum[k]=sum[k<<1]+sum[k<<1|1];
maxn[k]=max(maxn[k<<1],sum[k<<1]+maxn[k<<1|1]);
minn[k]=min(minn[k<<1],sum[k<<1]+minn[k<<1|1]);
}
void build(int k,int l,int r)
{
if(l==r)
{
int a=read();
if(!(l&1)) a=-a;
sum[k]=a,maxn[k]=max(0,a),minn[k]=min(0,a);
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
up(k);
}
void update(int k,int l,int r,int x,int a)
{
if(l==r)
{
if(!(l&1)) a=-a;
sum[k]=a,maxn[k]=max(0,a),minn[k]=min(0,a);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x,a);
else update(k<<1|1,mid+1,r,x,a);
up(k);
}
int solve(int x,int k,int l,int r)
{
if(l==r) return (int)max(0ll,min((ll)S,x+sum[k]));
int mid=(l+r)>>1,rc=k<<1|1;
if(maxn[rc]-minn[rc]>S) return solve(0,k<<1|1,mid+1,r);
x=solve(x,k<<1,l,mid);
if(x+maxn[rc]>S) return S+sum[rc]-maxn[rc];
if(x+minn[rc]<0) return sum[rc]-minn[rc];
return x+sum[rc];
}
int main()
{
// freopen("stone3.in","r",stdin);
// freopen("stone3_my.out","w",stdout);
n=read(),q=read(),X=read(),Y=read(),S=X+Y;
build(1,1,n);
while(q--)
{
int opt=read();
if(opt==1) X=read(),S=X+Y;
if(opt==2) Y=read(),S=X+Y;
if(opt==3)
{
int p=read(),v=read();
update(1,1,n,p,v);
}
printf("%d\n",solve(X,1,1,n));
}
return 0;
}