CF1150D Three Religions

完了我已经掉成Pupil了..

考虑对于每次询问做一个DP处理。

设$f(i,j,k)$表示使得串1的前i位，串2的前j位，串2的前k位能在主串中同时不相交出现的最短的前缀长度。

设$g(n,ch)$表示第n个字符之后，ch第一次出现的位置，如果不存在则设为$\infty$。

转移时考虑$f(i,j,k)=min(g([i\geq 1]f(i-1,j,k),S_1(i)),g([j\geq 1]f(i,j-1,k),S_2(j)),g([k\geq 1]f(i,j,k-1),S_3(k)))$。

边界条件$f(0,0,0)=0$。

可是这样单组询问复杂度是$O(250^3)$的，尽管这也是个常数。

但是注意到每组询问要么是追加一个字符，要么是删除末尾的字符。

假设在第i个串后追加一个字符，那么只需要把第i个串的DP数组推进一维即可。

删除第i个串末尾的字符，只需要把DP数组其他两维置INF。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <cstring>
#include <assert.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;
const int_t INF = 0x7fffffff;
const int_t LARGE = 250;
//µÚn¸ö×Ö·ûºó£¬×Ö·ûcµÚÒ»´Î³öÏÖµÄλÖÃ
int first[100001][26];
int dp[251][251][251];
int pos[4];
int strs[4][252];
char str[100010];
int n,m;
int at(int pos,char chr) {
#ifdef DEBUG
	cout<<"at "<<pos<<" "<<chr<<" = ";
#endif
	if(pos>n) {
#ifdef DEBUG
		cout<<0x3f3f3f3f<<endl;
#endif
		return 0x3f3f3f3f;
	}
#ifdef DEBUG
	cout<<first[pos][chr-'a']<<endl;
#endif
	return first[pos][chr-'a'];
}
int main() {
//    cin >> n >> m;
	scanf("%d%d%s",&n,&m,str + 1);
	memset(first[n],0x3f,sizeof(first[n]));
//	cout<<first[n][1]<<endl;
	for(int_t i = n; i >= 1; i --) {
		memcpy(first[i-1],first[i],sizeof(first[i]));
		first[i-1][str[i]-'a']=i;

	}
#ifdef DEBUG
	for(int i=0; i<n; i++) for(char chr='a'; chr<='d'; chr++) cout<<"first "<<i<<" "<<chr<<" = "<<first[i][chr-'a']<<endl;

#endif
	memset(dp,0x3f,sizeof(dp));
	dp[0][0][0]=0;
	for(int i=1; i<=m; i++) {
		static char opt[3];
		int id;
		scanf("%s%d",opt,&id);
		if(opt[0]=='+') {
			char chr,strx[3];
			scanf("%s",&strx);
			chr=strx[0];
			strs[id][++strs[id][0]]=chr;
			int len=strs[id][0];
			if(id==1) {
//				for(int i=0; i<=strs[1][0]; i++)
				{
					int i=strs[1][0];
					for(int j=0; j<=strs[2][0]; j++) {
						for(int k=0; k<=strs[3][0]; k++) {
							if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
							if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
							if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
							cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
						}
					}
				}
			} else if(id==2) {
				for(int i=0; i<=strs[1][0]; i++) {
//				for(int j=0; j<=strs[2][0]; j++)
					int j=strs[2][0];
					{
						for(int k=0; k<=strs[3][0]; k++) {
							if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
							if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
							if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
							cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
						}
					}
				}
			} else {
				for(int i=0; i<=strs[1][0]; i++) {
					for(int j=0; j<=strs[2][0]; j++) {
						int k=strs[3][0];
//					for(int k=0; k<=strs[3][0]; k++)
						{
							if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
							if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
							if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
							cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
						}
					}
				}
			}
		} else {

			if(id==1) {
				for(int j=0; j<=strs[2][0]; j++)
					for(int k=0; k<=strs[3][0]; k++) {
						dp[strs[id][0]][j][k]=INF;
					}
			} else if(id==2) {
				for(int i=0; i<=strs[1][0]; i++)
//                for(int j=1;j<=strs[2][0];j++)
					for(int k=0; k<=strs[3][0]; k++) {
						dp[i][strs[2][0]][k]=INF;
					}

			} else {
				for(int i=0; i<=strs[1][0]; i++)
					for(int j=0; j<=strs[2][0]; j++) {
//			        for(int k=1;k<=strs[3][0];k++){
						dp[i][j][strs[3][0]]=INF;
					}

			}
			strs[id][0]--;
		}
		if(dp[strs[1][0]][strs[2][0]][strs[3][0]]<=n) {
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}
	return 0;
}