solution - AT_abc415_f

v[pos].mx=max(lc.mx,rc.mx);
v[pos].la=lc.la,v[pos].l=lc.l,v[pos].ra=rc.ra,v[pos].r=rc.r;
if(lc.r==rc.l) chmax(v[pos].mx,lc.ra+rc.la);
if(lc.r==rc.l && lc.op && rc.op) v[pos].la=v[pos].ra=lc.la+rc.ra,v[pos].op=1;
else v[pos].op=0;
if(lc.r==rc.l && lc.op) chmax(v[pos].la,lc.la+rc.la);
if(lc.r==rc.l && rc.op) chmax(v[pos].ra,rc.ra+lc.ra);

int n,Q,a[N];
string s;

class __segment_tree
{
#define lc v[pos<<1]
#define rc v[pos<<1|1]
#define lcp pos<<1
#define rcp pos<<1|1
	
private:
	
	int *a,n;
	struct node{int mx,la,l,ra,r; bool op;} v[N<<2];
	int k,lt,rt;
	
	il void pushup(int pos)
	{
		v[pos].mx=max(lc.mx,rc.mx);
		v[pos].la=lc.la,v[pos].l=lc.l,v[pos].ra=rc.ra,v[pos].r=rc.r;
		if(lc.r==rc.l) chmax(v[pos].mx,lc.ra+rc.la);
		if(lc.r==rc.l && lc.op && rc.op) v[pos].la=v[pos].ra=lc.la+rc.ra,v[pos].op=1;
		else v[pos].op=0;
		if(lc.r==rc.l && lc.op) chmax(v[pos].la,lc.la+rc.la);
		if(lc.r==rc.l && rc.op) chmax(v[pos].ra,rc.ra+lc.ra);
	}
	
	il node merge(node a,node b)
	{
		if(a.mx==-1) return b;
		if(b.mx==-1) return a;
		
		node c;
		c.mx=max(a.mx,b.mx);
		c.la=a.la,c.l=a.l,c.ra=b.ra,c.r=b.r;
		if(a.r==b.l) chmax(c.mx,a.ra+b.la);
		if(a.r==b.l && a.r==b.r && a.r==a.l && a.op && b.op) c.la=c.ra=a.la+b.ra,c.op=1;
		else c.op=0;
		if(a.r==b.l && a.op) chmax(c.la,a.la+b.la);
		if(a.r==b.l && b.op) chmax(c.ra,b.ra+a.ra);
		
		return c;
	}
	
	il void build(int l,int r,int pos)
	{
		if(l==r) return v[pos]={1,1,a[l],1,a[l],1},void();
		int mid=l+r>>1;
		build(l,mid,lcp),build(mid+1,r,rcp);
		pushup(pos);
	}
	
	il void update(int l,int r,int pos)
	{
		if(l>=lt && r<=rt) return v[pos]={1,1,k,1,k,1},void();
		int mid=l+r>>1;
		mid>=lt && (update(l,mid,lcp),1);
		mid+1<=rt && (update(mid+1,r,rcp),1);
		pushup(pos);
	}
	
	il node query(int l,int r,int pos)
	{
		if(l>=lt && r<=rt) return v[pos];
		int mid=l+r>>1; node res={-1};
		mid>=lt && (res=merge(query(l,mid,lcp),res),1);
		mid+1<=rt && (res=merge(res,query(mid+1,r,rcp)),1);
		return res;
	}
	
public:
	il void bui(int _n) {build(1,n,1);}
	il void bui(int *_a,int _n) {a=_a,n=_n,build(1,n,1);}
	il void upd(int l,int r,int _k) {l>r && (swap(l,r),1); k=_k,lt=l,rt=r; update(1,n,1);}
	il int q(int l,int r) {l>r && (swap(l,r),1); lt=l,rt=r; return query(1,n,1).mx;}
	
#undef lc
#undef rc
#undef lcp
#undef rcp
} tr;

il void solve()
{
	read(n,Q),read(s),s="$"+s;
	rep(i,1,n) a[i]=s[i];
	
	tr.bui(a,n);
	
	int op,l,r,p; char x;
	while(Q--)
	{
		read(op);
		if(op==1) read(p),read(x),tr.upd(p,p,x);
		else read(l,r),write(tr.q(l,r),'\n');
	}
}