题解-CF163E e-Government

题面

CF163E e-Government

给 \(n\) 个字符串 \(s_i\) 和 \(q\) 个询问，刚开始字符串都服役。每次操作将集合中的一个字符串设为退役或服役，或查询与文本串 \(S_i\) 的匹配的服役字符串总次数。

数据范围：\(1\le n,q\le 10^5\)，\(1\le \sum|s_i|,\sum|S_i|\le 10^6\)。

蒟蒻语

这是个AC自动机的套路题，但是毕竟套路巧妙而且不得不学，所以蒟蒻写一篇题解。

蒟蒻解

当这题的字符串不退役时，这就是AC自动机的模板。

回忆一下蒟蒻们是怎么做的：先建一棵Trie树，在有字符串终止节点的位置 \(tag=1\)。然后考虑到包含一个字符串必然包含一个字符串的后缀，建立 \(fail\) 链成为AC自动机，\(fail\) 链连接节点成为 \(parent\) 树，重算一个节点的 \(tag\) 为它在 \(parent\) 树上到根节点的路径上的节点的 \(tag\) 之和。每次匹配的时候，在AC自动机上跑一遍文本串，累计一下 \(tag\) 即可。

让一个字符串退役，就相当于将该字符串在Trie树上的终止节点 \(p\) 的 \(tag=1\) 变成 \(tag=0\)。建AC自动机重算 \(tag\) 的时候，每个在 \(parent\) 树上到根节点的路径上包含 \(p\) 的节点的 \(tag\) 都会减 \(1\)。容易发现 \(tag\) 减了 \(1\) 的节点，正好就是 \(parent\) 树上 \(p\) 的子树。

这时候就可以做了，巨佬可以写个树链剖分或LinkCutTree。但是考虑到这题只需要操作子树，不需要操作链，所以可以不写轻重链剖分，求每个节点的 \(dfs\) 序及其子树的 \(dfs\) 序区间即可。区间修改、单点查询可以用差分加树状数组。

当然这题有很多细节，而且代码很长，估计能写写调调好久……看蒟蒻代码吧。

代码

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair(a,b)

#define x first

#define y second

#define be(a) a.begin()

#define en(a) a.end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=1e5,M=1e6+1;

int n,at[N];

bool vis[N];

//FenwickTree

int c[M+2];

void add(int x,int v){

	for(int i=x+1;i<M+2;i+=i&-i) c[i]+=v;

}

int sum(int x){

	int res=0;

	for(int i=x+1;i>=1;i-=i&-i) res+=c[i];

	return res;

}

//ACAM

int cnt=1,ch[M][26];

void insert(int x,string&s){

	int p=0;

	for(int i=0;i<sz(s);i++){

		int c=s[i]-'a';

		if(!~ch[p][c]) ch[p][c]=cnt++;

		p=ch[p][c];

	}

	at[x]=p; //记录第x个字符串的终止节点，方便查找dfs序

}

int fa[M],ind,ld[M],rd[M];//[ld,rd)是自动机节点的子树dfs序区间，ld正好是该节点的dfs序

vector<int> e[M];

void Dfs(int p){

	ld[p]=ind++;

	for(int v:e[p]) Dfs(v);

	rd[p]=ind;

}

void build(){

	queue<int> q;

	for(int c=0;c<26;c++)

		if(~ch[0][c]){

			fa[ch[0][c]]=0;

			e[0].pb(ch[0][c]); //加边建parent树

			// cout<<0<<"->"<<ch[0][c]<<'\n';

			q.push(ch[0][c]);

		} else ch[0][c]=0;

	while(sz(q)){

		int p=q.front(); q.pop();

		for(int c=0;c<26;c++)

			if(~ch[p][c]){

				fa[ch[p][c]]=ch[fa[p]][c];

				e[fa[ch[p][c]]].pb(ch[p][c]); //加边建parent树

				// cout<<fa[ch[p][c]]<<"->"<<ch[p][c]<<'\n';

				q.push(ch[p][c]);

			} else ch[p][c]=ch[fa[p]][c];

	}

	Dfs(0);

}

//Main

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int T; cin>>T>>n;

	for(int p=0;p<M;p++){

		fa[p]=-1;

		for(int c=0;c<26;c++) ch[p][c]=-1;

	}

	for(int i=0;i<n;i++){

		string s; cin>>s;

		insert(i,s);

	}

	build();

	for(int i=0;i<n;i++) //刚开始字符串都服役

		vis[i]=1,add(ld[at[i]],1),add(rd[at[i]],-1);

	while(T--){

		char c;	cin>>c;

		if(c=='+'){

			int i; cin>>i,--i;

			if(vis[i]) continue;

			vis[i]=1,add(ld[at[i]],1),add(rd[at[i]],-1);

		} else if(c=='-'){

			int i; cin>>i,--i;

			if(!vis[i]) continue;

			vis[i]=0,add(ld[at[i]],-1),add(rd[at[i]],1);

		} else if(c=='?'){

			string s; cin>>s;

			int res=0,p=0;

			for(int i=0;i<sz(s);i++){

				int c=s[i]-'a';

				p=ch[p][c],res+=sum(ld[p]);

			}

			cout<<res<<'\n';

		}

	}

	return 0;

}

祝大家学习愉快！

巴特西

题解-CF163E e-Government

题面

蒟蒻语

蒟蒻解

代码

最新文章

热门文章