QOJ6504 Flower's Land 2 题解

题目链接：QOJ6504 Flower's Land 2

题意：

给定一个只包含 \(0,1,2\) 的序列，\(T\) 次询问，询问有两种：

• 区间所有数加 \(1\) 然后模 \(3\)
• 求一段区间能否通过每次删掉相邻两个相同的数删完（如 \(1,0,0,2,2,1\) 就满足条件）

题解：

考虑用什么方法来维护区间能否消完，如果有一个东西能满足结合律但并不满足交换律的话，就可以全部乘起来看一下能否消完。而矩阵刚好就满足这样的条件，所以用一个线段树维护区间的矩阵乘积即可。

具体的，随机三个互逆的矩阵。因为要互相消掉的两个位置下标一定不同奇偶，所以可以在 \(i\mod 2=0\) 时用矩阵 \(A\)，\(=1\) 时用矩阵 \(A^{-1}\)。每个区间维护三个值，分别是原来的矩阵乘积，整体加一后的乘积，加二后的乘积，修改的话整个区间三个数轮换一下就行了。

而代码中，我用的是对合矩阵（即自己和自己互逆），这样就不用奇偶分类讨论。而构造这类矩阵也很简单，只需要记住一个结论，二阶对合矩阵都满足 \(\begin{pmatrix}a&b\\ \frac{1-a^2}{b}&-a\end{pmatrix}\) 这样的结构。具体怎么推的，随便令一个矩阵 \(\begin{pmatrix}a&b\\c&d\end{pmatrix}\) 乘一下就可以了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
using namespace std;
const int N = 5e5+5,mod = 1e9+7;
int a[N],n,q;
char s[N];
struct matrix
{
	int a[2][2];
	friend matrix operator *(matrix a,matrix b)
	{
		matrix c;memset(c.a,0,sizeof c.a);
		for(int i = 0;i < 2;i++)
			for(int j = 0;j < 2;j++)
				c.a[i][j] = (1ll*a.a[i][0]*b.a[0][j]+1ll*a.a[i][1]*b.a[1][j])%mod;
		return c;
	}
}m[3],E,t[N << 2][3];
int tag[N << 2];
void update(int x){for(int i = 0;i < 3;i++)t[x][i] = t[ls][i]*t[rs][i];}
void build(int x,int l,int r)
{
	if(l==r)
	{
		for(int i = 0;i < 3;i++)t[x][i] = m[(a[l]+i)%3];
		return ;
	}
	int mid = l+r>>1;
	build(lson);build(rson);update(x);
}
void change(int x){swap(t[x][0],t[x][1]);swap(t[x][1],t[x][2]);}
void pushdown(int x)
{
	if(!tag[x])return ;
	(tag[ls] += tag[x]) %= 3;(tag[rs] += tag[x]) %= 3;
	for(int i = 1;i <= tag[x];i++)change(ls),change(rs);
	tag[x] = 0;
}
void modify(int x,int l,int r,int L,int R)
{
	if(L <= l&&r <= R){(tag[x] += 1) %= 3;change(x);return ;}
	pushdown(x);
	int mid = l+r>>1;
	if(L <= mid)modify(lson,L,R);
	if(mid < R)modify(rson,L,R);
	update(x);
}
matrix query(int x,int l,int r,int L,int R)
{
	if(L <= l&&r <= R)return t[x][0];
	int mid = l+r>>1;
	pushdown(x);matrix ans = E;
	if(L <= mid)ans = query(lson,L,R);
	if(mid < R)ans = ans*query(rson,L,R);
	return ans;
}
bool cmp(matrix x){return x.a[0][0]==1&&x.a[0][1]==0&&x.a[1][0]==0&&x.a[1][1]==1;}
//cmp是用来判断是不是单位矩阵的
void init()
{
	m[0] = {998244353,353442899,610614424,1755654};
	m[1] = {114514,1919810,358338529,999885493};
	m[2] = {123456789,987654321,866052702,876543218};
	E = {1,0,0,1};
}
inline int rd()
{
	char c;int f = 1;
	while((c = getchar()) < '0'||c > '9')if(c=='-')f = -1;
	int x = c-'0';
	while('0' <= (c = getchar())&&c <= '9')x = x*10+(c^48);
	return x*f;
}
//ll qp(ll x,int y)
//{
//	ll ans = 1;
//	for(;y;y >>= 1,x = x*x%mod)
//		if(y&1)(ans *= x) %= mod;
//	return ans;
//}
int main()
{
//	ll aa = rd(),bb = rd();
//	cout << (1-aa*aa%mod+mod)*qp(bb,mod-2)%mod << ',' << mod-aa;
	n = rd();q = rd();scanf("%s",s+1);
	init();
	for(int i = 1;i <= n;i++)a[i] = s[i]-'0';
	build(1,1,n);
	while(q--)
	{
		int op = rd(),l = rd(),r = rd();
		if(op == 1)modify(1,1,n,l,r);
		else puts(cmp(query(1,1,n,l,r))?"YES":"NO");
	}
	return 0;
}