求助,珂朵莉树,只过了两个HACK点,其余全WA
查看原帖
求助,珂朵莉树,只过了两个HACK点,其余全WA
993122
xiaorunrun520楼主2024/10/7 17:24

调了好久,全是对的点判成错,还都是在比较靠后的询问出错

#include<bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
int n,m;
char ch[500005];
struct node{
	int l,r;
	mutable char col;
	node(int L,int R=-1,int Col=0): l(L),r(R),col(Col) {}
	bool operator <(const node &A) const {
		return l<A.l;
	}
};
set<node> s;
IT split(int pos){
	IT it = s.lower_bound(node(pos));
	if(it!=s.end() && it->l == pos) return it;
	it--;
	int L=it->l, R=it->r;
	int col = it->col;
	s.erase(it);
	s.insert(node(L,pos-1,col));
	return s.insert(node(pos,R,col)).first;
}
void assign(int l,int r,char col){
	IT itr = split(r+1), itl = split(l);
	s.erase(itl,itr);
	s.insert(node(l,r,col));
}
bool query(int l,int r){
	IT itr = split(r+1), itl = split(l);
	bool f = 1;
	IT it=itl;
	if(prev(it)->col == itr->col){
		f=0;
	}
	for(;it!=itr;it++){
		if(it->col != itl->col){
			f=0;
			break;
		}
	}
	char col=itl->col;
	int L=itl->l ,R=prev(it)->r;
	s.erase(itl,it);
	s.insert(node(L,R,col));
	return f;
}
void debug(){
	for(IT it=s.begin();it!=s.end();it++){
		cout<<it->l<<" "<<it->r<<" "<<it->col<<endl;
	}
}
int main(){
	scanf("%d",&n);
	scanf("%s",ch+1);
	int la = 1;
	s.insert(node(0,0,'#'));
	s.insert(node(n+1,n+1,'&'));
	for(int i=2;i<=n+1;i++){
		if(ch[i]!=ch[i-1]){
			s.insert(node(la,i-1,ch[i-1]));
			la = i;
		}
	}
	scanf("%d",&m);
	char opt,x;
	int l,r;
	while(m--){
		scanf("%s",&opt);
		if(opt=='A'){
			scanf("%d%d%s",&l,&r,&x);
			assign(l,r,x);
		}
		else{
			scanf("%d%d",&l,&r);
			if(query(l,r)) printf("Yes\n");
			else printf("No\n");
		}
		//debug();
	}
	return 0;
}
2024/10/7 17:24
加载中...