問題の解法

クエリを直接見ると、\(k=0\) の場合、区間の最大連続部分列を維持すればよい。

\(k=1\) の場合を考える。

元の配列:
.>>!|&>>?
変更後:
!<<.|?<<&

見にくい？回転してみる：（答えは変わらない）

&>>?|.>>!

気づいたか？区間の切り替えは二つの部分を交換することと等価である。つまり、先頭と末尾が同じときのみ結果に寄与し、それは接頭辞＋接尾辞となる。（ただし、すべて同じ要素の場合、答えは \(r-l+1\) になる）

この考えを拡張すると、\(k>1\) も \(k=1\) と同じである。

例を挙げる：

方法1: 元の配列
.>>!|&>>?
変更1:
&>>?|.>>!
変更2:
!|&>>?>>.

方法2: 元の配列
.|!>>&>>?
変更後:
!>>&>>?|.

データ構造

セグメント木を使用して以下を管理する：

コード

#include
#define int long long
using namespace std;
const int N=2e5+5;
struct node{
int vp,vs;
int pre,suf;
int mx;
int len;
int tag;
node(int l=0):len(l){
vp=vs=0;
pre=suf=0;
mx=tag=0;
return;
}
}tr[N<<2],kong;
int n,m;
int a[N];
void push_up(int p){
tr[p].vp=tr[p<<1].vp;
tr[p].vs=tr[p<<1|1].vs;
tr[p].pre=tr[p<<1].pre;
tr[p].suf=tr[p<<1|1].suf;
if(tr[p].pre==tr[p<<1].len&&tr[p<<1].vs==tr[p<<1|1].vp)
tr[p].pre+=tr[p<<1|1].pre;
if(tr[p].suf==tr[p<<1|1].len&&tr[p<<1].vs==tr[p<<1|1].vp)
tr[p].suf+=tr[p<<1].suf;
tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
if(tr[p<<1].vs==tr[p<<1|1].vp)
tr[p].mx=max(tr[p].mx,tr[p<<1].suf+tr[p<<1|1].pre);
return;
}
void push_down(int p){
if(tr[p].tag){
tr[p<<1].vp=tr[p<<1].vs=tr[p<<1].tag=tr[p].tag;
tr[p<<1].mx=tr[p<<1].pre=tr[p<<1].suf=tr[p<<1].len;
tr[p<<1|1].vp=tr[p<<1|1].vs=tr[p<<1|1].tag=tr[p].tag;
tr[p<<1|1].mx=tr[p<<1|1].pre=tr[p<<1|1].suf=tr[p<<1|1].len;
tr[p].tag=0;
}
return;
}
void build(int p,int l,int r){
tr[p].len=r-l+1;
if(l==r){
tr[p].vp=tr[p].vs=a[l];
tr[p].mx=tr[p].pre=tr[p].suf=1;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
return;
}
void assign(int p,int l,int r,int x,int y,int v){
if(y>1;
push_down(p);
assign(p<<1,l,mid,x,y,v);
assign(p<<1|1,mid+1,r,x,y,v);
push_up(p);
return;
}
node query(int p,int l,int r,int x,int y){
if(y>1;
push_down(p);
node res;
node tmpl=query(p<<1,l,mid,x,y);
node tmpr=query(p<<1|1,mid+1,r,x,y);
if(tmpl.len==0)	return tmpr;
if(tmpr.len==0)	return tmpl;
res.len=tmpr.len+tmpl.len;
res.pre=tmpl.pre;
res.suf=tmpr.suf;
res.vp=tmpl.vp;
res.vs=tmpr.vs;
if(res.pre==tmpl.len&&tmpl.vs==tmpr.vp)
res.pre+=tmpr.pre;
if(res.suf==tmpr.len&&tmpl.vs==tmpr.vp)
res.suf+=tmpl.suf;
res.mx=max(tmpl.mx,tmpr.mx);
if(tmpl.vs==tmpr.vp)
res.mx=max(res.mx,tmpl.suf+tmpr.pre);
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--){
char op;
int l,r,k;
cin>>op>>l>>r>>k;
if(op=='R'){
assign(1,1,n,l,r,k);
}
if(op=='Q'){
node t=query(1,1,n,l,r);
int ans=t.mx;
if(k>0&&t.vp==t.vs)
ans=min(r-l+1,max(ans,t.pre+t.suf));
cout<