Description
在石头剪刀布中，一共有三种手势：\(R(Rock), P(Paper), S(Scissors)\)，其中 \(R\) 能赢 \(S\)，\(S\) 能嬴 \(P\)，\(P\) 能赢 \(R\)。
现在，我们定义 \(w(x, y)\) 是 \(x\) 和 \(y\) 中获胜的手势，特别地，如果 \(x\) 和 \(y\) 相同（也就是平局），那么 \(w(x, y)\) 也和 \(x, y\) 均相同。\(x\) 和 \(y\) 均为 \(R, P, S\) 中的某一种。
我们定义一个对长度为 \(n\) 的字符串 \(s\) 的操作 \(f\left(s_1 s_2 \ldots s_n\right)=w\left(s_1, s_2\right) w\left(s_2, s_3\right) \ldots w\left(s_{n-1}, s_n\right)\)，也就是说操作结果是一个长度为 \(n-1\) 的字符串，它的第 \(i\) 位恰是 \(w\left(s_i, s_{i+1}\right)\)，也就是 \(s_i\) 和 \(s_{i+1}\)中获胜的手势。如 \(f(R R R R)=R R R, f(R S P R)=R S P\)。
我们定义一个长度为 \(n\), 且由 \(R, P, S\) 组成的字符串的“最终胜者”是对这个字符串进行连续 \(n-1\) 次 \(f\) 操作得到的结果，它显然是某个长度为 \(1\) 的字符串，并且是 \(R, P, S\) 中的一种。
现在，给定一个长度为 \(n\) 的字符串，你需要支持 \(q\) 次操作，操作有两种：
\(1\ k\ x\)：将这个字符串的第 \(k\) 个字符修改为 \(x\)，\(k\) 是 \(1-n\) 之间的整数，\(x \in R, P, S\)。
\(2\ l\ r\)：查询这个字符串的第 \(l\) 个字符到第 \(r\) 个字符形成的连续子串的“最终胜者”，\(1 \leq l \leq r \leq n\)。
\(n,q\le 2\times 10^5\)。
Solution
先不考虑修改，看看全局查询怎么做。
对于一个连续的相同段来说，如果其左右两边都是可以赢它的，那么这个连续段就可以直接变成赢它的那个字符。例如，SRRRRS 就可以直接变成 SSSSSS。
同时，若以 \(1\) 为开头的一段连续串，其右边是可以赢它的，同样可以将连续串变成赢它的那个字符。同理，以 \(n\) 为结尾的也是一样。
每进行一次上面那个操作，就会少至少一个连续段。可以证明，若干次操作后，整个串会变成一个连续串。
证明：假设最后剩下了至少两个连续串，不妨设有 \(k\) 个。那么一定有第 \(1\) 个能赢第 \(2\) 个，第 \(2\) 个一定能赢第 \(3\) 个。因此类推，第 \(k-1\) 个一定能赢第 \(k\) 个，这样第 \(k\) 个串就能被转换，与原设矛盾。因此最后一定只剩下一个串。
现在考虑对某一个字串进行求解。考虑维护一个栈，记栈底的元素为元素 \(1\)，那么使得元素 \(i\) 能赢 \(i-1\)。每次插入元素时，弹出栈顶直到空栈或者栈顶可以赢待插入的元素。那么扫完字串后，栈底元素即为“最终胜者”。时间复杂度 \(\mathcal O(nq)\)。
考虑数字化这个过程。设 \(f_i\) 表示加入当前元素后栈的大小。那么有
\(f_i=\begin{cases}f_{i-1}+1&s_i>s_{i-1}\bigcup i=1\\f_i&s_i=s_{i-1}\\\max(1,f_{i-1}-1)&s_i<s_{i-1}\end{cases}\)
\(x>y\) 表示 \(x\) 能赢 \(y\)，\(=\) 表示相等，\(<\) 表示 \(x\) 输给 \(y\)。
那么答案就为最后的 \(f_i=1\) 的 \(s_i\)。
但是，与 \(1\) 取 \(\max\) 是难维护的。你考虑定义一个广泛的栈，这个栈是可以有负下标的。那么就不再需要取 \(\max\)，同时答案变成了最小的 \(f_i\)。同时你发现，那些最小的 \(f_i\) 的 \(s_i\) 是相同的。
那么考虑维护 \(f_i\) 的差分 \(d_i\)，然后找一个前缀最小值即可。那么现在就是单点修改，区间前缀最小值。用取和的操作转为区间修改加查询区间最小值位置。上线段树即可。复杂度 \(\mathcal O(q\log n)\)。
Code
#include<cstdio>
#define N 200005
#define inf 0x3f3f3f3f
using namespace std;
struct segtree
{
int val,pos;
}tr[N<<2];
int n,m,a[N],d[N],sum[N],lz[N<<2];
char s[N];
char itc(int x)
{
if (x==0) return 'R';
if (x==1) return 'S';
if (x==2) return 'P';
}
int cti(char x)
{
if (x=='R') return 0;
if (x=='S') return 1;
if (x=='P') return 2;
}
bool pd(int x,int y)
{
if (x==0&&y==1) return true;
if (x==1&&y==2) return true;
if (x==2&&y==0) return true;
return false;
}
void build(int x,int l,int r)
{
if (l==r) {tr[x].val=sum[l];tr[x].pos=l;return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
if (tr[x<<1].val<=tr[x<<1|1].val) tr[x]=tr[x<<1];
else tr[x]=tr[x<<1|1];
}
void pushdown(int x)
{
if (lz[x]!=0)
{
tr[x<<1].val+=lz[x];lz[x<<1]+=lz[x];
tr[x<<1|1].val+=lz[x];lz[x<<1|1]+=lz[x];
lz[x]=0;
}
}
void modify(int x,int l,int r,int p,int q,int v)
{
if (l>=p&&r<=q)
{
tr[x].val+=v;
lz[x]+=v;
return;
}
pushdown(x);
int mid=(l+r)>>1;
if (mid>=p) modify(x<<1,l,mid,p,q,v);
if (mid<q) modify(x<<1|1,mid+1,r,p,q,v);
if (tr[x<<1].val<=tr[x<<1|1].val) tr[x]=tr[x<<1];
else tr[x]=tr[x<<1|1];
}
segtree query(int x,int l,int r,int p,int q)
{
if (l>=p&&r<=q) return tr[x];
pushdown(x);
int mid=(l+r)>>1;segtree res;
res.val=inf;res.pos=0;
if (mid>=p) res=query(x<<1,l,mid,p,q);
if (mid<q)
{
if (res.val>=inf) res=query(x<<1|1,mid+1,r,p,q);
else
{
segtree ress=query(x<<1|1,mid+1,r,p,q);
if (ress.val<res.val) res=ress;
}
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for (int i=1;i<=n;++i)
a[i]=cti(s[i]);
d[1]=1;
for (int i=2;i<=n;++i)
{
if (pd(a[i-1],a[i])) d[i]=1;
else if (pd(a[i],a[i-1])) d[i]=-1;
else d[i]=0;
}
for (int i=1;i<=n;++i)
sum[i]=sum[i-1]+d[i];
build(1,1,n);
while (m--)
{
int ty;
scanf("%d",&ty);
if (ty==1)
{
int x;scanf("%d",&x);
char ch=getchar();
while (ch!='R'&&ch!='S'&&ch!='P') ch=getchar();
int bef,aft,now=cti(ch);
if (x!=1)
{
bef=d[x];aft=0;
if (pd(a[x-1],now)) aft=1;
if (pd(now,a[x-1])) aft=-1;
d[x]=aft;
modify(1,1,n,x,n,aft-bef);
}
if (x!=n)
{
bef=d[x+1];aft=0;
if (pd(now,a[x+1])) aft=1;
if (pd(a[x+1],now)) aft=-1;
d[x+1]=aft;
modify(1,1,n,x+1,n,aft-bef);
}
a[x]=now;
}
else
{
int x,y;scanf("%d%d",&x,&y);
printf("%c\n",itc(a[query(1,1,n,x,y).pos]));
}
}
return 0;
}