Deltix Round Autumn 2021 : E. William The Oblivious

やらかした回。
https://codeforces.com/contest/1609/problem/E

問題

abcで構成される文字列Sがある。
Sを1文字置き換えるクエリが与えられるので、そのつど下記を答えよ。

• Sを何文字か置き換えて(不連続でもよい)部分列に'abc'が含まれないようにするため、最小の置き換えも次数

解法

SegTreeの要領で、連続部分列中にa,b,c,ab,bc,abcができないようにする最小文字数を数えていく。

int N,Q;
string S;

const int NV=1<<20;
int val[2*NV][6];

void update(int entry,int c) {
	entry += NV;
	int i;
	FOR(i,6) val[entry][i]=0;
	val[entry][c]=1;
	while(entry>1) {
		entry>>=1;
		int X=2*entry;
		int Y=X+1;
		val[entry][0]=val[X][0]+val[Y][0];
		val[entry][1]=val[X][1]+val[Y][1];
		val[entry][2]=val[X][2]+val[Y][2];
		val[entry][3]=min({val[X][0]+val[Y][3],val[X][3]+val[Y][1]});
		val[entry][4]=min({val[X][1]+val[Y][4],val[X][4]+val[Y][2]});
		val[entry][5]=min({val[X][0]+val[Y][5],val[X][5]+val[Y][2],val[X][3]+val[Y][4]});
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>S;
	FOR(i,N) {
		S[i]-='a';
		update(i,S[i]);
	}
	
	FOR(i,Q) {
		cin>>x>>s;
		x--;
		S[x]=s[0]-'a';
		update(x,S[x]);
		cout<<val[1][5]<<endl;
		
	}
	
}

まとめ

なぜ本番であんなに手間取ったのか…。