炸鸡块君与FIFA22

炸鸡块君与FIFA22

tag:

• 2100
• 线段树 st表分块

题意： 给定一个长度为 n 的字符串，m 次询问，每次询问 [ l , r ] 区间以起始 s 分的最终得分 得分规则为遇到 W 加一分，遇到 D 分数不变，遇到 L 若此时分数不是 3 的倍数则减一分

解： 考虑线段树，一个线段树维护三个状态，分别代表到这场比赛的之前的分数对三的余数（0 1 2 ）。因此根节点的维护方案就是左区间值为右区间起点数值，左右区间之和减去多算的一次左区间终点余数得分。

因此查询也要左右分开查询，左边查询的结果作为右边的初始值。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
//#define int  ll
#define endl '\n'
#define IOS                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0)
using namespace std;
int read()
{
	int res = 0, flag = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			flag = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		res = (res << 3) + (res << 1) + (ch ^ 48); //res*10+ch-'0';
		ch = getchar();
	}
	return res * flag;
}
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-8;
struct sgt
{
	int sco[3]; // 以 x%3 分为起始的得分
} a[maxn << 2];
int n, m;
string s;
#define ls root << 1
#define rs root << 1 | 1
void pushup(int root)
{
	for(int i = 0 ; i< 3 ; i++)
	a[root].sco[i] = a[ls].sco[i] / 3 * 3 + a[rs].sco[a[ls].sco[i] % 3];
}
void build(int root = 1, int l = 1, int r = n)
{
	if (l == r)
	{
		if (s[l] == 'W')
		{
			a[root].sco[0] = 1;
			a[root].sco[1] = 2;
			a[root].sco[2] = 3;
		}
		if (s[l] == 'L')
		{
			a[root].sco[0] = 0;
			a[root].sco[1] = 0;
			a[root].sco[2] = 1;
		}
		if (s[l] == 'D')
		{
			a[root].sco[0] = 0;
			a[root].sco[1] = 1;
			a[root].sco[2] = 2;
		}
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(root);
}
int query(int root, int l, int r, int ql, int qr, int val)
{
	if (l > qr || r < ql)
		return 0;
	if (l >= ql && r <= qr)
		return a[root].sco[val];
	int mid = l + r >> 1, res = 0, flag = 0;
	if (ql <= mid)
		res = query(ls, l, mid, ql, qr, val), flag = 1;
	if (qr > mid)
	{
		if (flag)
			res = res /3 * 3 + query(rs, mid + 1, r, ql, qr, res % 3);
		else
			res = query(rs, mid + 1, r, ql, qr, val);
	}
	return res;
}
int main()
{
	n = read(), m = read();
	cin >> s;
	s = " " + s;
	build();
	while (m--)
	{
		int l = read(), r = read(), s = read();
		printf("%d\n", query(1, 1, n, l, r, s % 3) + s / 3 * 3);
	}
	return 0;
}