二进制分组扩展

最近才发现的一个套路，以前以为二进制分组只能搞背包，结果发现还有一些更为优秀的操作。

我们对于一个不支持动态操作的数据结构，拆分为 \(log\) 个，然后每次加入元素加入到一个新的组中，如果最新的两个数据结构元素个数相等，就合并两个元素。然后暴力重构这个合并得到的数据结构。

然后查询的时候就查询每一个分组内的答案，之后答案合并即可。

我们可以证明，这样的操作的复杂度是 \(O(QlogQ)\) ，Q是操作个数。

相当于积累一个技巧。

例题 CF710

这个题我们就考虑二进制分组AC自动机。然后就可以支持动态插入。之后我们对于被删除的字符串开一个AC自动机的二进制分组。查询的时候答案就是原二进制分组的答案减去被删除的字符串的二进制分组的答案。

#include
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout)
template
inline void read(T &s){
	s=0;char ch=getchar();bool f=0;
	while(ch<'0'||'9'c;
	inline void del(int x){
		if(!fail[x]) return;
		fail[x]=val[x]=0;
		delnode(x);
		for(int i=0;i<26;++i){
			del(ch[x][i]);
			ch[x][i]=0;
		}
	}
	inline void clear(){
		del(rt);rt=newnode();c.clear();tot=0;
	}
	inline void ins(std::string s){
		c.push_back(s);++tot;
	}
	inline void build(){
		del(rt);rt=newnode();
		for(auto s:c){
			int len=s.size();
			int p=rt;
			for(int i=0;iq;
		while(!q.empty() ) q.pop();
		fail[rt]=rt;
		for(int i=0;i<26;++i){
			if(ch[rt][i]){
				q.push(ch[rt][i]);
				fail[ch[rt][i] ]=rt;
			}
		}
		while(!q.empty() ){
			int u=q.front();q.pop();
			for(int i=0;i<26;++i){
				int cr=ch[fail[u] ][i];
				if(!cr) cr=rt;
				if(ch[u][i]) fail[ch[u][i] ]=cr,q.push(ch[u][i]);
				else ch[u][i]=cr;
			}
			val[u]+=val[fail[u] ];
		}
	}
	inline int query(std::string s){
		int len=s.size(),p=rt;
		int ans=0;
		for(int i=0;i1 and A[top1].tot==A[top1-1].tot){
		for(auto it:A[top1].c){
			A[top1-1].ins(it);
		}
		A[top1].clear();
		--top1;
	}
	A[top1].build();
}
inline void del(std::string s){
	++top2;B[top2].clear();B[top2].ins(s);
	while(top2>1 and B[top2].tot==B[top2-1].tot){
		for(auto it:B[top2].c){
			B[top2-1].ins(it);
		}
		B[top2].clear();
		--top2;
	}
	B[top2].build();
}
inline int query(std::string s){
	int res=0;
	for(int i=1;i<=top1;++i){
		res+=A[i].query(s);
	}
	for(int i=1;i<=top2;++i){
		res-=B[i].query(s);
	}
	return res;
}
int Q;
std::string c;
int main(){
	//filein(a);fileot(a);
	read(Q);
	while(Q--){
		int op;read(op);
		std::cin>>c;
		if(op==1){
			ins(c);
		}else if(op==2){
			del(c);
		}else{
			int ans=query(c);
			printf("%d\n",ans);
			sky;
		}
	}
	return 0;
}