线段树WA求调
查看原帖
线段树WA求调
290055
jr_inf楼主2023/9/6 10:47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
//#define int long long
//#define int unsigned long long
using namespace std;
//const int p=415411;
const int iinf=2147483647;
const long long linf=9223372036854775807;
const int N=5e5+10;
int n,k,t[N*4][3],tag[N*4],nt;
char ch[N],op[1],type[1];
void downtag(int o,int l,int r)
{
	if(tag[o]==-1)return;
	t[o][(tag[o]+1)%3]=t[o][(tag[o]+2)%3]=0;
	t[o][tag[o]]=r-l+1;
	tag[o*2]=tag[o*2+1]=tag[o];
	tag[o]=-1;
}
int get(int o)
{
	if(t[o][0]+t[o][1]==0)return 2;
	if(t[o][1]+t[o][2]==0)return 0;
	if(t[o][0]+t[o][2]==0)return 1;
	return -1;
}
void update(int o,int l,int r,int x,int y,int v)
{
	if(r<x||y<l)return;
	if(x<=l&&r<=y)
	{
		tag[o]=v;
		return;
	}
	downtag(o,l,r);
	int mid=(l+r)>>1;
	update(o*2,l,mid,x,y,v);
	update(o*2+1,mid+1,r,x,y,v);
	t[o][0]=t[o*2][0]+t[o*2+1][0];
	t[o][1]=t[o*2][1]+t[o*2+1][1];
	t[o][2]=t[o*2][2]+t[o*2+1][2];
}
void build(int o,int l,int r)
{
	tag[o]=-1;
	if(l==r)
	{
		t[o][ch[l-1]-'A']++;
		return;
	}
	int mid=(l+r)>>1;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	t[o][0]=t[o*2][0]+t[o*2+1][0];
	t[o][1]=t[o*2][1]+t[o*2+1][1];
	t[o][2]=t[o*2][2]+t[o*2+1][2];
}
bool query(int o,int l,int r,int x,int y)
{
	downtag(o,l,r);
	if(r<x||y<l)return 1;
	if(x<=l&&r<=y)
	{
		if(nt==-1)nt=get(o);
		if(get(o)!=nt||get(o)==-1)return 0;
		return 1;
	}
	int mid=(l+r)>>1;
	return query(o*2,l,mid,x,y)&&query(o*2+1,mid+1,r,x,y);
}
int query2(int o,int l,int r,int x)
{
	downtag(o,l,r);
	if(l==r)return get(o);
	int mid=(l+r)>>1;
	if(x<=mid)return query2(o*2,l,mid,x);
	else return query2(o*2+1,mid+1,r,x);
}
bool check(int x,int y)
{
	if(x<1||y>n)return 1;
	return query2(1,1,n,x)!=query2(1,1,n,y);
}
signed main()
{
	scanf("%d %s%d",&n,ch,&k);
	build(1,1,n);
	while(k--)
	{
		int x,y;
		scanf(" %s%d%d",op,&x,&y);
		if(op[0]=='A')
		{
			scanf(" %s",type);
			update(1,1,n,x,y,type[0]-'A');
		}
		if(op[0]=='B')nt=-1,puts((check(x-1,y+1)&&query(1,1,n,x,y))?"Yes":"No");
	}
}
2023/9/6 10:47
加载中...