洛谷CF1609E求调(Unknown Error)
  • 板块题目总版
  • 楼主gf20231114
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/5/2 14:02
  • 上次更新2024/5/2 18:01:56
查看原帖
洛谷CF1609E求调(Unknown Error)
1246864
gf20231114楼主2024/5/2 14:02

加了各种注释还是未知错误

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,maxq=1e5+5;
int n,q;
char c[maxn];
struct node{
	int l,r,A,B,C,AB,BC,ABC;
}tr[maxn<<2];
void push_up(int id){
	tr[id].A=tr[id<<1].A+tr[id<<1|1].A;
	tr[id].B=tr[id<<1].B+tr[id<<1|1].B;
	tr[id].C=tr[id<<1].C+tr[id<<1|1].C;
	tr[id].AB=min(tr[id<<1].A+tr[id<<1|1].AB,tr[id<<1].AB+tr[id<<1|1].B);
	tr[id].BC=min(tr[id<<1].B+tr[id<<1|1].BC,tr[id<<1].BC+tr[id<<1|1].C);
	tr[id].ABC=min({tr[id<<1].A+tr[id<<1|1].ABC,tr[id<<1].AB+tr[id<<1|1].BC,tr[id<<1].ABC+tr[id<<1|1].C});
}void build(int id,int l,int r){
	tr[id].l=l,tr[id].r=r;
	if(l==r){
		if(c[l]=='a'){
			tr[id].A=1;
		}else if(c[l]=='b'){
			tr[id].B=1;
		}else{
			tr[id].C=1;
		}
	}else{
		const int mid=l+r>>1;
		build(id<<1,l,mid);
		build(id<<1|1,mid+1,r);
		push_up(id);
	}
}void up_date(int id,int pos,char val){
	if(tr[id].l==pos&&tr[id].r==pos){
		if(val=='a'){
			tr[id].A=1,tr[id].B=0,tr[id].C=0;
		}else if(val=='b'){
			tr[id].A=0,tr[id].B=1,tr[id].C=0;
		}else{
			tr[id].A=0,tr[id].B=0,tr[id].C=1;
		}
	}else{
		const int mid=tr[id].l+tr[id].r>>1;
		if(mid>=pos){
			up_date(id<<1,pos,val);
		}else{
			up_date(id<<1|1,pos,val);
		}push_up(id);
	}
}int query(int id,int l,int r){
	if(tr[id].l>=l&&tr[id].r<=r){
		return tr[id].ABC;
	}else{
		const int mid=tr[id].l+tr[id].r>>1;
		int ret=0;
		if(mid>=l){
			ret+=query(id<<1,l,r);
		}if(mid<r){
			ret+=query(id<<1|1,l,r);
		}push_up(id);
		return ret;
	}
}int main(){
	cin.tie(0);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}build(1,1,n);
	for(int i=1;i<=q;i++){
		int id;
		char change;
		scanf("%d",&id);
		cin>>change;
		up_date(1,id,change);
		printf("%d\n",query(1,1,n));
	}
	return 0;
}/*
water problem
*/
2024/5/2 14:02
加载中...