Description
\(N\) 个人排成一排， 每个人都事先决定出剪刀、石头、布。
每次可以任意选两个相邻的人进行决斗。 规则和游戏一样。
但是如果平局， 则掷硬币来决定胜负。 输的人下场。
现要求出有几个人 有获胜的可能（即可以任意决定决斗的顺序 和 掷出的硬币）
Solution
一个很显然的结论： 一个人要想获胜， 两边都要满足其中一个条件， 以左边为例：
左边没有能赢他的人， 或者 左边存在一个他能赢的人即可。
根据这个结论， 我们分别计算出剪刀 、石头、 布的人有多少人能赢。
以计算出剪刀有多少人能赢为例， 先找出最先出布的人和最后出布的人， 这两个人中间的人都可以赢， 记入贡献
然后再剩余出剪刀的人 左边没有人出石头 和 右边没有人出石头的人的个数。
用\(Bit\)和\(Set\) 可以\(O(logN)\)计算。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#define up(a, b) (a = a > b ? a : b)
#define down(a, b) (a = a > b ? b : a)
#define cmax(a, b) (a > b ? a : b)
#define cmin(a, b) (a > b ? b : a)
#define Abs(a) ((a) > 0 ? (a) : -(a))
#define lowbit(x) ((x) & -(x))
#define rd read()
#define db double
#define LL long long
using namespace std;
typedef pair<int, int> P;
/*
inline char nc(){
static char buf[1<<14],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline LL read(){
char c=nc();LL x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
return x*f;
}
*/
int read() {
int X = 0, p = 1; char c = getchar();
for (; c > '9' || c < '0'; c = getchar())
if (c == '-') p = -1;
for (; c >= '0' && c <= '9'; c = getchar())
X = X * 10 + c - '0';
return X * p;
}
const int N = 2e5 + 5;
int n, m, sum[4][N];
char s[N];
set<int> S[4];
int ch(char c) {
if (c == 'R')
return 0;
if (c == 'P')
return 1;
if (c == 'S')
return 2;
}
void add(int x, int d, int *p) {
for (; x <= n; x += lowbit(x))
p[x] += d;
}
int query(int x, int *p) {
if (x < 0) return 0;
int res = 0;
for (; x; x -= lowbit(x))
res += p[x];
return res;
}
int work(int x) {
int y = (x + 2) % 3; //x > y
int z = (x + 1) % 3; //z > x
int res = 0;
if (!S[y].size()) {
if (S[z].size())
return 0;
else return n;
}
int l = *(S[y].begin()), r = *(--S[y].end());
if (S[y].size() > 1)
res += query(r, sum[x]) - query(l - 1, sum[x]);
int tmp = S[z].size() ? *(S[z].begin()) : n + 1;
down(tmp, l);
res += query(tmp, sum[x]);
tmp = S[z].size() ? *(--S[z].end()) : 0;
up(tmp, r);
res += query(n, sum[x]) - query(tmp - 1, sum[x]);
return res;
}
int main()
{
n = rd; m = rd;
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
add(i, 1, sum[ch(s[i])]);
S[ch(s[i])].insert(i);
}
printf("%d\n", work(0) + work(1) + work(2));
for (int i = 1; i <= m; ++i) {
int x = rd; char c = getchar();
for (; !(c == 'R' || c == 'P' || c == 'S');)
c = getchar();
S[ch(s[x])].erase(x); add(x, -1, sum[ch(s[x])]);
s[x] = c;
S[ch(s[x])].insert(x); add(x, 1, sum[ch(s[x])]);
printf("%d\n", work(0) + work(1) + work(2));
}
}