锰锌钢学线段树,样例过了但0pts,求条
查看原帖
锰锌钢学线段树,样例过了但0pts,求条
729338
xihegudiiakioi楼主2024/8/20 13:46
#include <bits/stdc++.h>
#define maxn 500010
#define ls (x << 1)
#define rs ((x << 1) | 1)
#define mid ((l + r) >> 1)
#define int long long
#define endl "\n"
using namespace std;

int n,m;
int s[maxn << 2],lazy[maxn << 2];
string str;
void up(int x){
	if(s[ls] == s[rs]){
		s[x] = s[ls];
	}else{
		s[x] = 0;
	}
}
void build(int x,int l,int r){
	if(l == r){
		s[x] = str[l - 1] - 'A' + 1;
		return ;
	}
	build(ls,l,mid);
	build(rs,mid + 1,r);
	up(x);
}
void push_down(int x){
	lazy[ls] = lazy[rs] = lazy[x];
	s[ls] = s[rs] = lazy[x];
	lazy[x] = 0;
}
void modify(int x,int l,int r,int L,int R,int tag){
	if(L <= l && r <= R){
		lazy[x] = tag;
		s[x] = tag;
		return ;
	}
	if(lazy[x]){
		push_down(x);
	}
	if(L <= mid){
		modify(ls,l,mid,L,R,tag);
	}
	if(R >= mid + 1){
		modify(rs,mid + 1,r,L,R,tag);
	}
	up(x);
}
int query(int x,int l,int r,int L,int R){
	if(L <= l && r <= R){
	    return s[x];
	}
	if(lazy[x]){
		push_down(x);
	}
	int ret = -1,res = -1;
	if(L <= mid){
	    res = query(ls,l,mid,L,R);
	}
	if(R >= mid + 1){
		ret = query(rs,mid + 1,r,L,R);
	}
	if(ret == 0 || res == 0){
		return 0;
	}
	if(res == -1 && ret == -1){
		return -1;
	}
	if(res == -1){
		return ret;
	}
	if(ret == -1){
		return res;
	}
	if(ret != res){
		return 0;
	}
	if(ret == res){
		return res;
	}
}
signed main(){
	cin >> n;
	cin >> str;
	cin >> m;
	build(1,1,n);
	char op;
	for(int i = 1,x,y,z;i <= m;i++){
		cin >> op;
		if(op == 'A'){
			cin >> x >> y >> z;
			modify(1,1,n,x,y,z);
		}else{
			cin >> x >> y;
			if(query(1,1,n,x,y) == 0){
				cout << "No" << endl;
				continue;
			}
			int left = -1,right = -1;
			if(x - 1 >= 1){
				left = query(1,1,n,x - 1,x - 1);
			}
			if(y + 1 <= n){
				right = query(1,1,n,y + 1,y + 1);
			}
			if(left != right){
				cout << "Yes" << endl;
			}else{
				cout << "No" << endl;
			}
		}
	}
}
2024/8/20 13:46
加载中...