2022牛客寒假第一场炸鸡块君与FIFA22 （线段树）_随笔

2022牛客寒假第一场炸鸡块君与FIFA22 （线段树）

题目链接：点击这里

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

题目分析：
我们可以用线段树维护区间 [ l , r ] [l,r] [l,r] 以 x m o d 3 xmod 3 xmod3 分为起始分的最终得分
对于 pushup text{pushup} pushup 来说根节点的值可以用左区间的值-对 3 3 3 的余数，再加上用右区间以这个余数为起始分数的最终得分即可
对于查询，我们分左右两个区间来查，如果左区间查询了，那么查右区间的起始分数应该是左区间的得分，如果没查起始分数就是函数传进来的参数

具体细节见代码：

// Problem: 炸鸡块君与FIFA22
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/B
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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;
void pushup(int root)
{
	a[root].sco[0] = a[root<<1].sco[0]-a[root<<1].sco[0]%3+a[root<<1|1].sco[a[root<<1].sco[0]%3];
	a[root].sco[1] = a[root<<1].sco[1]-a[root<<1].sco[1]%3+a[root<<1|1].sco[a[root<<1].sco[1]%3];
	a[root].sco[2] = a[root<<1].sco[2]-a[root<<1].sco[2]%3+a[root<<1|1].sco[a[root<<1].sco[2]%3];
}
void build(int root,int l,int r)
{
	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(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
int query(int root,int l,int r,int ql,int qr,int val)
{
	if(l>qr || r=ql && r<=qr) return a[root].sco[val];
	int mid = l+r>>1,res = 0,flag = 0;
	if(ql <= mid) res = query(root<<1,l,mid,ql,qr,val),flag = 1;
	if(qr > mid)
	{
		if(flag) res = res-res%3+query(root<<1|1,mid+1,r,ql,qr,res%3);
		else res = query(root<<1|1,mid+1,r,ql,qr,val);
	}
	return res;
}
int main()
{
	n = read(),m = read();
	cin>>s;
	s = " "+s;
	build(1,1,n);
	while(m--)
	{
		int l = read(),r = read(),s = read();
		printf("%dn",query(1,1,n,l,r,s%3)+s-s%3);
	}
	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5713567.html

2022牛客寒假第一场炸鸡块君与FIFA22 （线段树）

发表评论

评论列表（0条）

2022牛客寒假第一场 炸鸡块君与FIFA22 （线段树）

发表评论

评论列表（0条）

2022牛客寒假第一场炸鸡块君与FIFA22 （线段树）