結果

問題 No.2992 Range ABCD String Query
コンテスト
ユーザー kotatsugame
提出日時 2024-12-25 10:13:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 264 ms / 6,000 ms
コード長 1,340 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 78,908 KB
実行使用メモリ 32,000 KB
最終ジャッジ日時 2024-12-25 10:13:35
合計ジャッジ時間 13,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<cassert>
#include<atcoder/segtree>
using namespace std;
struct dat{
	int a,ab,abc,abcd,b,bc,bcd,c,cd,d;
};
dat op(dat l,dat r)
{
	dat ret;
	ret.a=l.a+r.a;
	ret.ab=min(l.a+r.ab,l.ab+r.b);
	ret.abc=min({l.a+r.abc,l.ab+r.bc,l.abc+r.c});
	ret.abcd=min({l.a+r.abcd,l.ab+r.bcd,l.abc+r.cd,l.abcd+r.d});
	ret.b=l.b+r.b;
	ret.bc=min(l.b+r.bc,l.bc+r.c);
	ret.bcd=min({l.b+r.bcd,l.bc+r.cd,l.bcd+r.d});
	ret.c=l.c+r.c;
	ret.cd=min(l.c+r.cd,l.cd+r.d);
	ret.d=l.d+r.d;
	return ret;
}
dat e(){return(dat){};}
dat INIT[4];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	{//a
		dat v={};
		v.b=v.bc=v.bcd=v.c=v.cd=v.d=1;
		v.a=v.ab=v.abc=v.abcd=0;
		INIT[0]=v;
	}
	{//b
		dat v={};
		v.a=v.c=v.cd=v.d=1;
		v.b=v.ab=v.abc=v.abcd=v.bc=v.bcd=0;
		INIT[1]=v;
	}
	{//c
		dat v={};
		v.a=v.ab=v.b=v.d=1;
		v.c=v.bc=v.abc=v.abcd=v.bcd=v.cd=0;
		INIT[2]=v;
	}
	{//d
		dat v={};
		v.a=v.ab=v.abc=v.b=v.bc=v.c=1;
		v.abcd=v.bcd=v.cd=v.d=0;
		INIT[3]=v;
	}
	int N,Q;
	string S;
	cin>>N>>Q>>S;
	vector<dat>init(N);
	for(int i=0;i<N;i++)init[i]=INIT[S[i]-'A'];
	atcoder::segtree<dat,op,e>seg(init);
	for(;Q--;)
	{
		int OP;cin>>OP;
		if(OP==1)
		{
			int x;char c;
			cin>>x>>c;
			x--;
			seg.set(x,INIT[c-'A']);
		}
		else
		{
			int l,r;cin>>l>>r;
			dat t=seg.prod(l-1,r);
			cout<<t.abcd<<"\n";
		}
	}
}
0