Submission #67872524

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
#define cty cout<<"Yes"<<endl
#define ctn cout<<"No"<<endl
#define dbg(x) cout<<<<#x<<" : "<<x<<endl
#define int long long
const ll mod = 1e8;
const int mxn = 4e6+10;
struct node{
	int l,r,len,ls,rs,s;
	//左端点，右端点，区间长度
	//从左开始最长连续字符长度，从右开始最长连续字符长度，区间内最长连续字符长度
}t[mxn];
int n,q;
string s;
inline int lc(int i){
	return i<<1;
}
inline int rc(int i){
	return i<<1|1;
}
node pushup(node a,node b){
	//合并
	node t;
	t.l = a.l;
	t.r = b.r;
	t.len = t.r-t.l+1;
	t.ls = a.ls;
	t.rs = b.rs;
	t.s = max(a.s,b.s);
	if(s[a.r]==s[b.l]){
		t.s = max(t.s,a.rs+b.ls);
		if(a.ls==a.len) t.ls = a.len+b.ls;
		if(b.rs==b.len) t.rs = b.len+a.rs;
	}
	return t;
}
void build(int p,int l,int r){
	t[p] = {l,r,r-l+1,1,1,1};
	if(l==r) return;
	int mid = (l+r)/2;
	build(lc(p), l, mid);
	build(rc(p), mid+1, r);
	t[p] = pushup(t[lc(p)],t[rc(p)]);
}
void update(int p,int x){
	if(t[p].l==t[p].r) return;
	int mid = (t[p].l+t[p].r)/2;
	if(x<=mid) update(lc(p), x);
	else update(rc(p), x);
	t[p] = pushup(t[lc(p)], t[rc(p)]);
}
node query(int p,int l,int r){
	if(t[p].l>r||t[p].r<l) return {0,0,0,0,0,0};
	if(t[p].l>=l&&t[p].r<=r){
		return t[p];
	}
	return pushup(query(lc(p),l,r),query(rc(p),l,r));
}
void LonelyLunar_solve(){
	cin>>n>>q;
	cin>>s;
	s = " "+s;
	build(1,1,n);
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int i;
			char x;
			cin>>i>>x;
			s[i] = x;
			update(1,i);
		}
		else{
			int l,r;
			cin>>l>>r;
			cout<<query(1,l,r).s<<endl;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int _ = 1;
	//cin>>_;
	while(_--){
		LonelyLunar_solve();
	}
	return 0;
}

Submission Info

Judge Result