题解文字部分很长，知道大家不喜欢看，因此每一段我都会写下省流，有些部分你可以略读。

给一个（我场上胡的）单点修改线段树二分做法。时间复杂度与题目中的参数 $3$ 无关（即改成任何数都一样），预处理线性，修改单 $\log$，求答案单 $\log$，因此总复杂度 $O(n+q\log n)$。

省流：给个比较优秀的做法，让大家见笑了。

先考虑一些暴力的做法。大部分人第一个想到的正确做法应该是二分答案再暴力 dp check。直接做是 $O(qn^2\log n)$ 的，可以 bitset 优化但对正解没啥意义。有不少选手注意到了存在的连续段这个性质，可以获得 $35\sim 40$ pts。再往下就没有前途了，而我赛时可能代码能力不太够没写明白，干脆放弃了这个做法，去想下面的内容了。

省流：有一些暴力做法，不一定都对正解有帮助，所以我们接下来要取其精华。

首先保留刚才的二分结构，现在你二分到了 $k$，要判断其是否合法。我们先刻画出抽卡的结构。初始有 $$每一轮你可以摸 $1\sim 2$ 张牌，并打出一场攻击牌，一张防御牌或两张攻击牌。只有最后一次可能只摸 $1$ 张，所以在每次摸牌前，你手里都必然有 $k$ 张牌。

我们称每轮摸牌为一个回合，你需要挺过 $t$ 个回合，其中前至少 $t-1$ 个回合都是摸两牌。

省流：避免题目太玄幻，我们要用数学语言刻画下。

接下来，我们来定义几个数组变量：

$a_i,b_i$ 分别表示第 $i$ 回合将摸到多少张攻击牌/防御牌，$d_i=a_i+b_i,l_i=1-b_i,r_i=a_i-1$。$L_i,R_i$ 分别为 $l_i,r_i$ 的前缀和。根据这些定义你应该能看出，$\forall i<t,d_i=2,l_i=r_i,L_i=R_i$。以及为了体现做法对于技能冷却时间的普遍性，设 $z=3$。

设初始时的 $k$ 张牌中有 $h$ 张防御牌，则你能活下来，当且仅当存在一个序列 $c_{1\sim t}$ 表示每回合是否发动技能，满足：

• $\forall 1\leq i\leq t,c_i\in \{0,1\}$

• $\forall 1\leq i\leq t,h+(b_1-1+c_1)+(b_2-1+c_2)+\dots+(b_i-1+c_i)\geq 0$

• $\forall 1\leq i\leq t,k-h+(a_1-1-c_1)+(a_2-1-c_2)+\dots+(a_i-1-c_i)\geq 0$

• $\forall 1\leq x\leq y\leq t,y-x<z,c_x+\dots+c_y\leq 1$

省流：刻画完毕。

接下来我们稍微做做变形，设 $s_i=c_1+\dots+c_i$。不难证明，$c_i$ 不会取到浮点数，下面我们只去刻画其上下界。四个条件可以分别这样改写：

• $\forall 1\leq i\leq t,0\leq s_i-s_{i-1}\leq 1$

• $\forall 1\leq i\leq t,h-l_1-\dots-l_i+s_i-s_0\geq 0$

• $\forall 1\leq i\leq t,k-h+r_1+\dots+r_i-s_i+s_0\geq 0$

• $\forall 0\leq x<y\leq t,y-x\leq z,s_y-s_x\leq 1$

省流：我们已经可以转成前缀和的差分约束限制了，因为只要判无解，所以找负环即可。

建出 $t+1$ 个结点的图，则去除第一条和第四条限制的重复部分后，只剩了如下几种边：

• $\forall 1\leq i\leq t,i\xrightarrow{0}i-1$

• $\forall 1\leq i\leq t,i\xrightarrow{h-L_i}0$

• $\forall 1\leq i\leq t,0\xrightarrow{k-h+R_i}i$

• $\forall 0\leq x<y\leq t,y-x\leq z,x\xrightarrow{1}y$

称这四种边分别为一二三四类边。那么因为一四类边一定非负，不能只通过这类边搞出负环，所以一定要经过一次二三类边，因此一定要经过至少一次 $0$ 号点。而我们只在意简单负环，也就是经过 $0$ 号点恰好一次的环。

把二三类边经过的点记作关键点，则一四类边的作用是连接关键点，具体地，我们设 $\operatorname{dist}(x,y)$ 表示从 $x$ 只经过一四类边到达 $y$ 的最短路，则有：

$$\operatorname{dist}(x,y)=\max(0,\lceil\dfrac{y-x}{z}\rceil)$$

接下来我们根据是否经过二三类边，把环分为三类，则限制有如下几类：

• 只经过二类边：$\operatorname{dist}(0,x)+h-L_x\geq 0$

• 只经过三类边：$k-h+R_y+\operatorname{dist}(y,0)\geq 0$

• 都经过：$k-h+R_y+\operatorname{dist}(y,x)+h-L_x\geq 0$

省流：成功得到极其好写的 $O(qn^2\log n)$ 做法，前缀和优化就能得到小常数 $O(qn\log n)$ 的 40pts 了，而且很有前途！

再做变形，$\operatorname{dist}(x,y)=\lfloor\dfrac{\max(0,y-x+z-1)}{z}\rfloor$，于是又能改写：

• $\forall 1\leq x\leq t,x+z-1+z(h-L_x)\geq 0$

• $\forall 1\leq y\leq t,k-h+R_y\geq 0$

• $\forall 1\leq x<y\leq t,k+R_y-L_x\geq 0$

• $\forall 1\leq y<x\leq t,z(k+R_y-L_x)+x-y+z-1\geq 0$

到这里已经很接近正解了，不过我们还有一些遗留问题。也就是说，我们每次二分一个 $k$ 都要重新分回合，要维护的回合数量（也就是 $t$ 的总和）是 $O(n^2)$ 的，不就爆炸了吗？

此时你会注意到，阶段（即回合）本质不同只可能 $k$ 的奇偶性不同，因此你只需要分两类，奇数开头还是偶数开头。

具体地，如果 $n$ 是偶数，那么奇数开头的 $d$ 序列为 $122\dots221$，偶数为 $22\dots22$。$n$ 是奇数的话，奇数开头为 $122\dots22$，偶数开头为 $22\dots221$。

则二分的一个 $k$ 代表的是，已经完成了前面的一些阶段，你要用线段树维护一段后缀的信息。

省流：你要根据 $k$ 的奇偶性开两棵线段树，里面完全一样，所以只需要用结构体实现其中一个。下面讲线段树维护的具体细节，然后这个题就被成功解决了。

如果一起维护的话，开头位置就不是 $0$ 了，设为 $m$ 吧，则限制条件等价于。

• $\forall m<x\leq t,z\cdot h\geq -z+1+\sum\limits_{i=m+1}^{x}(z\cdot l_i-1)$

• $\forall m<y\leq t,z\cdot(k-h)\geq -z+1+\sum\limits_{i=y+1}^{m}(-z\cdot r_i)$

• $\forall m<x<y\leq t,z(k+(R_y-R_m)-(L_x-L_m))\geq -z+1$

• $\forall m<y<x\leq t,z(k+(R_y-R_m)-(L_x-L_m))+x-y\geq -z+1$

第三四条，根据我们很早就提到的性质分别有：

• $L_x-L_m=R_x-R_m$

• $R_y-R_m=L_y-L_m$

因此可以分别改写为：

• $\forall m<x<y\leq t,z(k+R_y-R_x)\geq -z+1$

• $\forall m<y<x\leq t,z(k+L_y-L_x)+x-y\geq -z+1$

因此四个条件也就是：

• $\forall m<x\leq t,z\cdot h\geq -z+1+\sum\limits_{i=m+1}^{x}(z\cdot l_i-1)$

• $\forall m<x\leq t,z\cdot(k-h)\geq -z+1+\sum\limits_{i=x+1}^{m}(-z\cdot r_i)$

• $\forall m<x<y\leq t,z\cdot k\geq -z+1+\sum\limits_{i=x+1}^{y}(-z\cdot r_i)$

• $\forall m<x<y\leq t,z\cdot k\geq -z+1+\sum\limits_{i=x+1}^{y}(z\cdot l_i-1)$

省流：发现这个条件很像最大子段和状物，因此你类似小白逛公园地，单点修改并分别维护每个节点 $(z\cdot l_i-1)$ 和 $(-z\cdot r_i)$ 的和、最大前后缀和、最大子段和共八个变量即可。

每次二分 $k$，用树状数组算出 $h$，线段树查询后缀可以做到 $O(n+q\log^2 n)$。我考场就写的这玩意，在 selfEval 上最大点 $1.6s$，感觉稳了，没再优化下去。

赛后重新写了一遍，发现其实可以直接线段树二分，因为信息的可加性很强，也显然有二分性。树状数组省去了，代码极短，加上我的快读板子也只有 $2.7K$，下面是我的代码：

#include<bits/stdc++.h>
using namespace std;
namespace file_read{
	char ib[1<<25],*ip1=ib,*ip2=ib;
	inline char gc(){
		return ((ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin))),ip1==ip2?EOF:*ip1++);
	}
	inline int read(){
		int x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
	char ob[1<<25],*op=ob;
	inline void pc(char c){
		*op++=c;
	}
	void write(int x){
		if(x>=10)write(x/10);
		pc(x%10+'0');
	}
	void final_write(){
		fwrite(ob,op-ob,1,stdout);
	}
}
using namespace file_read;
int cc,T,n,q,s[400005];
struct pear{
	int hl,hr,h;
	int qdr,hdr;
	int mx1,mx2;
	int qdl,hdl;
}pp;
pear operator+(pear a,pear b){
	pear c;
	c.hl=a.hl+b.hl,c.hr=a.hr+b.hr,c.h=a.h+b.h;
	c.hdr=max(b.hdr,a.hdr+b.hr);c.qdr=max(a.qdr,a.hr+b.qdr);
	c.mx2=max(max(a.mx2,b.mx2),a.hdr+b.qdr);
	c.hdl=max(b.hdl,a.hdl+b.hl);c.qdl=max(a.qdl,a.hl+b.qdl);
	c.mx1=max(max(a.mx1,b.mx1),a.hdl+b.qdl);
	return c;
}
struct apple{
	int t,L[100005],R[100005],K[100005];
	void jjj(int l,int r){
		int b=s[l]+(l<r&&s[r]),a=r-l+1-b;
		++t;L[t]=1-b,R[t]=a-1;K[t]=r;
	}
	pear sm[400005];
	void build(int l,int r,int o){
		if(l==r){
			sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
			sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
			sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
			sm[o].mx1=sm[o].mx2=-1e9;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,o<<1);build(mid+1,r,o<<1|1);
		sm[o]=sm[o<<1]+sm[o<<1|1];
	}
	void add(int l,int r,int o,int x){
		if(l==r){
			sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
			sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
			sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid)add(l,mid,o<<1,x);
		else add(mid+1,r,o<<1|1,x);
		sm[o]=sm[o<<1]+sm[o<<1|1];
	}
	void jia(int x,int y){
		L[x]-=y;R[x]-=y;add(1,t,1,x);
	}
	void init(int a){
		t=0;jjj(1,a);
		for(int i=a+1,j;i<=n;j=min(n,i+1),jjj(i,j),i=j+1);
		build(1,t,1);
	}
	int query(int l,int r,int o){
		if(l==r)return K[l];
		pear qq=sm[o<<1|1]+pp;
		int mid=(l+r)>>1,k=K[mid],h=sm[1].h-qq.h;
		if(3*k<max(qq.mx1,qq.mx2)-2||3*h<qq.qdl-2||3*(k-h)<qq.qdr-2)
			return query(mid+1,r,o<<1|1);
		pp=qq;return query(l,mid,o<<1);
	}
	int suan(){
		pp.mx1=pp.mx2=-1e9;
		pp.hdl=pp.hdr=0;pp.qdl=pp.qdr=-1e9;
		pp.hl=pp.hr=pp.h=0;
		return query(1,t,1);
	}
}e0,e1;
void solve(){
	write(min(e0.suan(),e1.suan()));
}
int main(){
	cc=read(),T=read();
	while(T--){
		n=read(),q=read();
		for(int i=1;i<=n;++i){
			char c2=gc();
			while(c2<'0'||c2>'9')c2=gc();
			s[i]=c2-'0';
		}
		e0.init(2);e1.init(1);solve();
		while(q--){
			int x=read(),aa=(s[x]^1)-s[x];s[x]^=1;
			e0.jia((x+1)/2,aa);e1.jia(x/2+1,aa);
			pc(' ');solve();
		}
		pc('\n');
	}
	final_write();
	return 0;
}

省流：这题做完了。

接下来考虑加强，从几个方向考虑：

• $3$ 显然可以改成任何数，一点区别都没有。

• 复杂度是单 $\log$ 的，因此可以加强到 $\sum n\leq 5\times 10^6,\sum q\leq 1\times 10^6$。

• 单点修改改为区间修改，应该存在一些分块做法。

作者码字不易，花费很多心血，留个赞再走吧，谢谢！有错误请尽情指出，感激不尽！