BZOJ 3881 Divljak

发表于 | 更新于

Cool。。

Link

(权限题。。一开始用小号交的时候显示：Where do find this link?No such problem.我就不说什么了。)

Description

Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。 接下来会发生q个操作，操作有两种形式： “1 P”，Bob往自己的集合里添加了一个字符串P。 “2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的子串） Bob遇到了困难，需要你的帮助。

Solution

嗯。。寻找集合TT中有多少串包含SxS_x，可以用Fail树做。 于是就把询问离线，把S,TS,T的字符串扔到一个Trie里然后跑出来AC自动机。建立了Fail树，对于一个询问xx，就转化为查询Fail树，SxS_x的末尾节点对应节点的子树中，存在多少表示TT中在此查询之前插入的串的节点，可以用线段树维护。 在建立AC自动机的时候，在Trie的每个节点记录有多少串包含了这个节点，O(L)O(L) 然后一遍DFS，加上线段树合并的复杂度，总共是O(Llogn)O(L\log n)。 写完之后交上去居然1A了。。 虽然这么暴力但跑的也不是很慢，11s。重载operator new之后快了1s。。只是内存占用超级大。。500M。。

正解

对SS建立AC自动机，建立Fail树。每个节点维护一个值，记录子树下有多少个T。 对于TT中的新串在AC自动机上跑，记录到达的节点。然后把Fail树中这些节点的值+1，把相邻点的LCA的值-1。查询就是子树和了。Orz。。又快又好写。。

Tips

只想出暴力离线的做法还是因为学得有些死板。一个串在AC自动机上跑到的节点，和在AC自动机上串的节点的性质其实是差不多的。

Code（新代码风格，欢迎拍砖吐槽）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10,SIZE=(2000000+10)<<1;
using std::pair;
using std::make_pair;

namespace iList
{
	template <class T> struct Node
	{
		Node *pre;T val;
		Node(Node *pre,T val):pre(pre),val(val){}
	};//*ME=(Node*)malloc(SIZE*sizeof(Node));
	template <class T> struct List
	{
		Node<T> *head;
		void Add(T v){head=new Node<T>(head,v);}
		void Clear(){head=0;}
	};
	List<int> G[SIZE],strs[SIZE];
	List<pair<int,int> > query[SIZE];
}using namespace iList;

namespace iAC
{
	const char SB='a',SE='z';
	const int SIGMA=SE-SB+1;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;
		int cnt;
		List<int> strs;
		Node *&next(char c){return son[c-SB];}
		Node(){memset(son,0,sizeof(son));fail=last=0;cnt=0;strs.Clear();}
		int num();
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*root=new(ME++) Node;
	Node* newNode(){return new(ME++) Node;}
	int Node::num(){return this-POOL+1;}
	Node* Insert(char *s,int c=0)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
			if(c) cur->strs.Add(c);
		}
		cur->cnt++;
		return cur;
	}
	void Build()
	{
		static Node *Q[SIZE];int he,ta;
		he=1,ta=0;root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}using namespace iAC;
namespace iSeg
{
	const int SIZE=MAXN<<2;
	int TL,TR;
	struct Node
	{
		Node *son[2];
		int v;
		Node(){v=0;}
		void up(){v=son[0]->v+son[1]->v;}
		bool isleaf(){return son[0]==son[1];}
	}*null=new Node,*ME=(Node*)malloc(SIZE*sizeof(Node));
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->v=0;cur->son[0]=cur->son[1]=null;
		cur->up();
		return cur;
	}
	Node *Merge(Node *a,Node *b)
	{
		if(a==null) return b;
		if(b==null) return a;
		assert(a->isleaf()==b->isleaf());
		if(a->isleaf() && b->isleaf())
			a->v=a->v|b->v;	
		else
		{
			Node *lc=Merge(a->son[0],b->son[0]),*rc=Merge(a->son[1],b->son[1]);
			a->son[0]=lc,a->son[1]=rc;a->up();
		}
		return a;
	}
	struct Seg
	{
		Node *root;
		Seg(Node *root=null):root(root){}
		int Access(Node *pos,int L,int R,int l,int r)
		{
			if(pos==null) return 0;
			if(L==l && R==r) return pos->v;
			else
			{
				int MID=(L+R)>>1;
				if(r<=MID) return Access(pos->son[0],L,MID,l,r);
				else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
				else return Access(pos->son[0],L,MID,l,MID)+Access(pos->son[1],MID+1,R,MID+1,r);
			}
		}
		void Edit(Node *&pos,int L,int R,int goal)
		{
			if(pos==null) pos=newNode();
			if(L==R) pos->v=1;
			else
			{
				int MID=(L+R)>>1;
				if(goal<=MID) Edit(pos->son[0],L,MID,goal);
				else Edit(pos->son[1],MID+1,R,goal);
				pos->up();
			}
		}
		void Edit(int pos){Edit(root,TL,TR,pos);}
		int Access(int l,int r){return Access(root,TL,TR,l,r);}
	};
	Seg Merge(Seg a,Seg b){return Seg(Merge(a.root,b.root));}			
}using namespace iSeg;
void InitTree()
{
	for(iAC::Node* ptr=iAC::POOL;ptr!=iAC::ME;++ptr)
	{
		if(ptr->fail!=ptr)//root!!!
			G[ptr->fail->num()].Add(ptr->num());
		strs[ptr->num()]=ptr->strs;
	}
}
int ANS[MAXN];
Seg DFS(int pos)
{
	Seg tree;
	for(iList::Node<int> *ptr=strs[pos].head;ptr;ptr=ptr->pre)
		tree.Edit(ptr->val);
	for(iList::Node<int> *ptr=G[pos].head;ptr;ptr=ptr->pre)
	{
		int u=ptr->val;
		tree=Merge(tree,DFS(u));
	}
	for(iList::Node<pair<int,int> > *ptr=query[pos].head;ptr;ptr=ptr->pre)
		ANS[ptr->val.second]=tree.Access(1,ptr->val.first);
	return tree;
}
int main()
{
	freopen("input","r",stdin);
	static char str[::SIZE];
	static iAC::Node *ref[MAXN];
	int n;get(n);
	for(int i=1;i<=n;i++) scanf("%s",str+1),ref[i]=Insert(str);
	int q,scnt=0;get(q);
	for(int i=1;i<=q;i++)
	{
		int opt,x;get(opt);
		if(opt==1) scanf("%s",str+1),Insert(str,++scnt),ANS[i]=-1;
		else get(x),query[ref[x]->num()].Add(make_pair(scnt,i));
	}
	TL=1,TR=scnt;
	Build();
	InitTree();
	int root=iAC::root->num();
	DFS(root);
	for(int i=1;i<=q;i++)
		if(~ANS[i]) printf("%d\n",ANS[i]);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */