蒟蒻线段树第十一个点WA求调
查看原帖
蒟蒻线段树第十一个点WA求调
355510
Lightwhite楼主2021/11/6 16:01
#include<bits/stdc++.h>
#define mid (l+r>>1)
#define int long long

using namespace std;

const int maxn=5e5+5;

int n,m,Tree[maxn<<2],Tag[maxn<<2],x,y,Val;
char ch[maxn],opt;

void Build(int rt,int l,int r){if(l==r) return Tree[rt]=1<<ch[l]-'A',void();Build(rt<<1,l,mid),Build(rt<<1|1,mid+1,r);Tree[rt]=Tree[rt<<1]|Tree[rt<<1|1];}
void Pushdown(int rt,int l,int r){if(Tag[rt]) Tree[rt<<1|1]=Tree[rt<<1]=Tag[rt<<1|1]=Tag[rt<<1]=Tag[rt],Tag[rt]=0;}

void Update(int rt,int l,int r){
	if(l>y||r<x) return ;
	if(l>=x&&r<=y) return Tree[rt]=Tag[rt]=Val,void();

	Pushdown(rt,l,r),Update(rt<<1,l,mid),Update(rt<<1|1,mid+1,r),Tree[rt]=Tree[rt<<1]|Tree[rt<<1|1];
}
int Query(int rt,int l,int r,int l2,int r2){
	if(l>r2||r<l2) return 0;
	if(l2<=l&&r<=r2) return Tree[rt];

	Pushdown(rt,l,r);return Query(rt<<1,l,mid,l2,r2)|Query(rt<<1|1,mid+1,r,l2,r2);
}

signed main(){
	scanf("%d %s %d",&n,ch+1,&m),Build(1,1,n);

	while(m--){scanf("\n%c %d %d",&opt,&x,&y);if(opt=='A') getchar(),Val=1<<getchar()-'A',Update(1,1,n);else puts(__builtin_popcount(Query(1,1,n,x,y))==1&&Query(1,1,n,x-1,x-1)!=Query(1,1,n,y+1,y+1)?"Yes":"No");}
	return 0;
}
2021/11/6 16:01
加载中...