题解

#include<bits/stdc++.h>
using namespace std;
namespace file_read{
char ib[1<<25],ip1=ib,ip2=ib;
inline char gc(){
return ((ip1ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin))),ip1ip2?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=3L[l]-1,sm[o].hr=-3R[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=3L[l]-1,sm[o].hr=-3R[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(3k<max(qq.mx1,qq.mx2)-2||3h<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;
}