MnZn妹子刚学oi114514ms,有注释,且马蜂不良
查看原帖
MnZn妹子刚学oi114514ms,有注释,且马蜂不良
1088663
zzzyyyyhhhhh楼主2024/5/12 19:56
#include<bits/stdc++.h>
using namespace std;
#define it set<node>::iterator 
const int N = 5e5+100;
int n,m;
struct node
{
	int l,r;
	mutable char var;
};
char in[N];
set<node> a;
bool operator<(node x,node y)
{
	return x.l<y.l;
}
it splite(int pos)//common splite
{
	it p=--a.upper_bound({pos,0,0});
	if((*p).l==pos)return p;
	int l=(*p).l,r=(*p).r;
	char c=(*p).var;
	a.erase(p);
	a.insert({l,pos-1,c});
	return a.insert({pos,r,c}).first;
}
it un(it p)//将此节点与前一个节点合并
{
	p--;
	it q=p;
	p++;
	int l=(*q).l,r=((*p)).r;
	char c=(*p).var;
	a.erase(p);
	a.erase(q);
	return a.insert({l,r,c}).first;
}
void op(int l,int r,char c)//修改某一段区间
{
	it p,q,m;//p,q,m分别为修改区间左边的区间,修改区间,修改区间右边的区间
	m=splite(r+1);
	q=splite(l);

	q++;
	for(;q!=m;q++)
	{
		q=un(q);
	}
	q--;
	((*q)).var=c;
	q--;
	p=q;
	q++;
	if((*q).var==(*m).var)un(m);
	if((*q).var==(*p).var)q=un(q);

	
	// ((*q)).var=c;
	// if(*p.var==(*q).var)q=un(p,q);
	// if((*q).var==*m.var)un(q,m);
}
bool find(int l,int r)
{
	it p=a.upper_bound({l,0,0});
	if(p!=a.upper_bound({r,0,0}))return 0;//是否在同一区间
	if(l==1||r==n)return 1;
	p--;
	char c,d;
	if(l==(*p).l)
	{
		p--;
		c=(*p).var;
		p++;
	}
	else c=(*p).var;
	if(r==(*p).r)
	{
		p++;
		d=(*p).var;
	}
	else d=(*p).var;
	return c!=d;//左右是否相同
}
int main()
{
	a.insert({1,n,in[1]});//init
	it q,p;
	cin>>n;
	cin>>in+1;
	for(int i=2;i<=n;i++)
	{
		if(in[i]!=in[i-1])
		{
			p=splite(i);
			p--;
			q=p;
			p++;
			(*q).var=in[i-1];
			(*p).var=in[i];
			// cerr<<"size"<<a.size()<<'\n';
		}
		//初始化,如果颜色不同就分为两段
	}
	cin>>m;
	char c;
	int x,y;
	char z;
	//操作
	for(int i=1;i<=m;i++)
	{
		cin>>c>>x>>y;
		if(c=='B')
		{
			if(find(x,y))
			{
				cout<<"Yes\n";
			}
			else
			{
				cout<<"No\n";
			}
		}
		else
		{
			cin>>z;
			op(x,y,z);
		}	
		// for(auto i:a)cerr<<i.l<<' ';

	}
}








2024/5/12 19:56
加载中...