提出 #67755837

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5;
constexpr int B=700;
constexpr int N_B=715;

int n,q;
string s;

int L[N+5],R[N+5],length[N+5];

int lc[N_B+5],rc[N_B+5],mc[N_B+5];

void upd(const int i,const int l,const int r){
	lc[i/B]=1;
	for(int j=l+1;j<=r;++j){
		if(s[j]==s[j-1]) ++lc[i/B];
		else break;
	}
	rc[i/B]=1;
	for(int j=r-1;j>=l;--j){
		if(s[j]==s[j+1]) ++rc[i/B];
		else break;
	}
	int tmp=1;
	for(int i=l+1;i<=r;++i){
		if(s[i]!=s[i-1]) mc[i/B]=max(mc[i/B],tmp),tmp=1;
		else ++tmp;
	}
	mc[i/B]=max(mc[i/B],tmp);
}

int query(const int l,const int r){
	int res=0,tmp;
	
	if(l/B==r/B){
		tmp=1;
		for(int i=l+1;i<=r;++i){
			if(s[i]!=s[i-1]) res=max(res,tmp),tmp=1;
			else ++tmp;
		}
		res=max(res,tmp);
		return res;
	}
	
	upd(l/B,l,R[l/B]),upd(r/B,L[r/B],r);
	res=mc[l/B],tmp=rc[l/B];
	
	for(int i=l/B+1;i<=r/B;++i){
		res=max(res,mc[i]);
		if(s[L[i]]!=s[R[i-1]]){
			res=max(res,tmp);
			tmp=rc[i];
		}
		else if(lc[i]!=length[i*B+1]){
			res=max(res,tmp+lc[i]);
			tmp=rc[i];
		}
		else tmp+=lc[i];
	}
	
	res=max(res,tmp);
	
	upd(l/B,L[l/B],R[l/B]),upd(r/B,L[r/B],R[r/B]);
	
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	
	cin>>n>>q;
	
	cin>>s;
	s=" "+s;
	
	for(int i=1;i<=n;++i){
		L[i]=i/B*B+1;
		R[i]=min(i/B*B+B,n);
		length[i]=R[i]-L[i]+1;
		if(i%B==0){
			upd(i,L[i/B],R[i/B]);
		}
	}
	
	int op;
	
	while(q--){
		cin>>op;
		
		if(op==1){
			int i;char x;
			cin>>i>>x;
			s[i]=x;
			upd(i,L[i/B],R[i/B]);
		}
		else if(op==2){
			int l,r;
			cin>>l>>r;
			cout<<query(l,r)<<endl;
		}
		else{
			cout<<"I AK IOI!!!"<<endl;
		}
	}
	
	return 0;
}

提出情報

ジャッジ結果