yukicoder : No.2992 Range ABCD String Query

まぁこれはだいぶ典型寄り。
https://yukicoder.me/problems/no/2992

問題

ABCDで構成される文字列Sが与えられる。
以下のクエリに順次答えよ。

• Sを1文字指定されたように更新する。
• Sの部分文字列が指定される。この文字列を、正規表現でいうと"A*B*C*D*"と一致するように書き換えたい。最小何文字書き換えればよいか。

解法

SegTreeで解く。
SegTreeの各ノードに、区間内に含まれる文字種の範囲と、それを満たすための最小コストを乗せる。
あとはそれらを更新したりクエリを実行したりすればよい。

struct node {
	int val[4][4];
};

node def;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		V m;
		int i,j,k;
		FOR(j,4) FOR(i,j+1) m.val[i][j]=1<<20;
		FOR(i,4) for(j=i;j<4;j++) for(k=j;k<4;k++) m.val[i][k]=min(m.val[i][k],l.val[i][j]+r.val[j][k]);
		return m;
	};
	
	SegTree_1(){val=vector<V>(NV*2);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, int v) {
		entry += NV;
		int i,j;
		FOR(j,4) FOR(i,j+1) val[entry].val[i][j]=(v<i||v>j);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<node,1<<18> st;
int N,Q;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,N) st.update(i,S[i]-'A');
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>S;
			st.update(x-1,S[0]-'A');
		}
		else {
			int L,R;
			cin>>L>>R;
			L--;
			auto ret=st.getval(L,R);
			cout<<ret.val[0][3]<<endl;
		}
	}
	
}

まとめ

わりとすんなり。