题解 | #炸鸡块君与FIFA22#

总之就是一道非常板子的题，可以用各种常见的具有分治结构的数据结构莽过去。

这里讲一下分块做法：不难发现扫过一段区间后 $ss$ 改变量只与位于段首时 $ss$ 模三的余数有关，则我们先将序列分成 $n^{0.5}n^\{0.5\}$ 个块，在各块首设 $s=0,1,2s=0,1,2$ 分别统计末位置的 $ss$，再分别减去 $1,2,31,2,3$ 即可得到块的改变量。统计答案时遇到完整的块就用改变量统计贡献，遇到残块就暴力统计，预处理 $O(n)O(n)$，单次统计答案 $O(n^{0.5})O(n^\{0.5\})$，总时间复杂度 $O(q\cdot n^{0.5})O(q·n^\{0.5\})$.

#include<cstdio>
#include<cstring>
#define mn 200005
#define mt 455
int n,q,t,bl[mn],l[mt],r[mt],del[mt][3];
char ch[mn];
int read() {
	int temp=0;
	char ch=getchar();
	while(ch<'!') ch=getchar();
	while(ch>'!') {
		temp=(temp<<3)+(temp<<1)+(ch^48);
		ch=getchar();
	}
	return temp;
}
void write(int temp) {
	if(temp>9) write(temp/10);
	putchar(temp%10|48);
}
int main() {
	n=read(); q=read();
	scanf("%s",ch+1);
	t=sqrt(n);
	for(int i=1; i<=n; ++i) bl[i]=(i-1)/t+1;
	for(int i=1; i<=bl[n]; ++i) l[i]=r[i-1]+1,r[i]=r[i-1]+t;
	r[bl[n]]=n;
	for(int i=1; i<=bl[n]; ++i) {
		for(int j=0; j<3; ++j) del[i][j]=j;
		for(int k=l[i]; k<=r[i]; ++k)
			for(int j=0; j<3; ++j) {
				switch(ch[k]) {
					case 'W': {
						++del[i][j];
						break;
					}
					case 'L': {
						if(del[i][j]%3) --del[i][j];
						break;
					}
				}
			}
		for(int j=0; j<3; ++j) del[i][j]-=j;
	}
	while(q--) {
		int le=read(),ri=read(),s=read();
		if(bl[le]==bl[ri]) {
			for(int k=le; k<=ri; ++k)
				switch(ch[k]) {
					case 'W': {
						++s;
						break;
					}
					case 'L': {
						if(s%3) --s;
						break;
					}
				}
		}
		else {
			for(int k=le; k<=r[bl[le]]; ++k)
				switch(ch[k]) {
					case 'W': {
						++s;
						break;
					}
					case 'L': {
						if(s%3) --s;
						break;
					}
				}
			for(int k=bl[le]+1; k<bl[ri]; ++k) s+=del[k][s%3];
			for(int k=l[bl[ri]]; k<=ri; ++k)
				switch(ch[k]) {
					case 'W': {
						++s;
						break;
					}
					case 'L': {
						if(s%3) --s;
						break;
					}
				}
		}
		write(s); putchar('\n');
	}
    return 0; 
}