珂朵莉树基础求调
查看原帖
珂朵莉树基础求调
734049
__Cby___楼主2024/1/12 13:02
#include <iostream>
#include <set>
using namespace std;
int n;
struct node{
	int l,r,v;
};
bool operator <(node a,node b){
	return a.l<b.l;
}
set<node> odt;
auto split(int x){
	if(x>n)return odt.end();
	auto it=--odt.upper_bound({x,0,0});
	if(it->l==x)return it;
	int l=it->l;
	int r=it->r;
	int v=it->v;
	odt.erase(it);
	odt.insert({l,x-1,v});
	return odt.insert({x,r,v}).first;
}
int assign(int l,int r,int v){
	auto itr=split(r+1);
	auto itl=split(l);
	auto ll=itl;
	auto rr=itr;
	ll--;
	rr++;
	if(ll->v==v){
		l=ll->l;
		itl=ll;
	}
	if(rr->v==v){
		r=rr->r;
		itr=rr;
	}
	odt.erase(itl,itr);
	odt.insert({l,r,v});
	return 0;
}
bool is(int l,int r){
	auto nowl=--odt.upper_bound({l,0,0});
	auto nowr=--odt.upper_bound({r,0,0});
	if(nowr!=nowl)return 0;
	if(!(l!=1&&r!=n))return 1;
	auto itl=nowl;
	auto itr=nowr;
	itl--;
	itr++;
	if(l>nowl->l&&r<nowr->r)return 0;
	if(l==nowl->l&&r==nowr->r){
		return itl->v!=itr->v;
	}
	if(l==nowl->l&&r<nowr->r){
		return itl->v!=nowr->v;
	}
	if(l>nowl->l&&r==nowr->r){
		return itr->v!=nowl->v;
	}
	return 1;
}
int main(){
	cin>>n;
	int tl=0;
	int dq=-1;
	for(int i=1;i<=n;i++){
		char a;
		cin>>a;
		int nw=a-'A'+1;
		if(dq!=nw){
		    odt.insert({tl,i-1,dq});
			dq=nw;
			tl=i;
		} 
	}
	odt.insert({tl,n,dq});
	odt.insert({n+1,n+1,-2});
	int q;
	cin>>q;
	while(q--){
		char a;
		cin>>a;
		if(a=='A'){
			int x,y;
			cin>>x>>y;
			char op;
			cin>>op;
			assign(x,y,op-'A'+1);
		}
		if(a=='B'){
			int x,y;
			cin>>x>>y;
			if(is(x,y)){
				cout<<"Yes"<<endl;
			}
			else{
				cout<<"No"<<endl;
			}
		}
	}
	return 0;
} 

10分,求调(或者简短的hack也行).
思路与第一篇题解一致

2024/1/12 13:02
加载中...