「HAOI2018」字串覆盖

发表于
字数统计: 2,330字 | 阅读时长 ≈ 12min

「HAOI2018」字串覆盖

题目描述

小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这样一个问题．

对于两个长度为 $n$ 的串 $A, B$ , 小C每次会给出给出 $4$ 个参数 $s, t, l, r$ . 令 $A$ 从 $s$ 到 $t$ 的子串(从 $1$ 开始标号)为 $T$，令 $B$ 从 $l$ 到 $r$ 的子串为 $P$.然后他会进行下面的操作：

如果 $T$ 的某个子串与 $P$ 相同，我们就可以覆盖 $T$ 的这个子串，并获得 $K - i$ 的收益，其中 $i$ 是初始时 $A$ 中(注意不是 $T$ 中)这个子串的起始位置，$K$是给定的参数．一个位置不能被覆盖多次．覆盖操作可以进行任意多次，你需要输出获得收益的最大值．

注意每次询问都是独立的，即进行一次询问后，覆盖的位置会复原．

输入格式

第一行两个整数 $n, K$ ，表示字符串长度和参数．

接下来一行一个字符串 $A$.

接下来一行一个字符串 $B$ .

接下来一行一个整数 $q$ ，表示询问个数．

接下来 $q$ 行，每行四个整数 $s, t, l, r$ ，表示一次询问．

输出格式

输出 $q$ 行，每行一个整数，表示一个询问的答案．

数据范围与提示

对于所有数据，有 $1 \le n, q \le 10^5$ ，$A, B$ 仅由小写英文字母组成，$1 \le s \le t \le n, 1 \le l \le r \le n, n < K \le 10^9$．

对于 $n = 10^5$ 的测试点，满足 $51 \le r - l \le 2000$ 的询问不超过 $11000$ 个，且 $r - l$ 在该区间内均匀随机．

貌似有后缀数组的优秀做法，但是蒟蒻只会后缀自动机……

首先容易想到，要获得最大收益，一定是采取这样的贪心策略：找到当前区间中左端点最小的用来覆盖的子串，再找到与它不交的下一个左端点最小的用来覆盖的子串……直到不能找到为止。

正确性说明：

由于$K>n$，所以每次收益一定是正的，那么单次价值显然是越靠前出现的越大。考虑这样一种情况：区间中第二靠左的子串与最左边的子串有交。那么如果要选第二的子串，那么剩下子串的选取方案对于最靠左的子串也是合法的。因此，每次选最靠左的一定是最优的。

那么现在只需要找到这些不交的出现位置即可，发现由于“不交”的限制很难直接用数据结构维护。那么考虑设置阈值（其实数据范围也有提示）。

用来覆盖的子串长度大于阈值时，用SAM暴力跳。具体做法是在两个串中间加一个分隔符建立SAM，用线段树合并弄出right集合。每次询问，用倍增找到自动机上$P[l,r]$对应的状态，再不断在它对应的线段树上找一找某个区间里出现的第一个位置就好。

当这个长度小于阈值的时候，考虑建图：用$id[i][j]$表示$T$中以$i$开头，长度为$j$的字符串代表的状态（这样的字符串需要是某个用来覆盖的串，否则没有意义），每个点向它右边第一个与它完全相同的字符串代表的状态连边，如果是第一次出现就连向0号点。容易看出这样形成了一棵树。对于每次询问，只需要倍增找到对应区间即可。

连边的处理需要开一个链表。在这里为了知道某个字符串右边第一次出现的位置，可以使用字符串hash+hash表（代码里采用的unordered_map）。

细节很多，码量很大，写起来很爆炸。考试时遇到这种题，应该先敲暴力，在前两道题都比较稳的情况下再写正解吧……

但是考场上真的能写对吗……

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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
#define ll unsigned long long
#define MAXN 400005
#define MAXT 10000005
#define MAXM 4000005
using namespace std;
const int LIM=50;
const ll sd=1234321237;

int N,K,Q;ll Ans[MAXN];char A[MAXN];

int srt,las,tot,mx[MAXN],par[MAXN][20],son[MAXN][27],pos[MAXN];
int rt[MAXN],ls[MAXT],rs[MAXT],sz[MAXT],seg_tot,seg_n;

ll ha[MAXN],hb[MAXN],pw[MAXN];
int nex[MAXN][LIM+3],id[MAXN][LIM+3],ori_beg[MAXT],id_tot;
unordered_map<ll,int>las_pos;
vector<int>save[MAXM];ll sum[MAXN];int D[MAXN];

int En[MAXN],Nex[MAXN],Las[MAXN],Tot;
int EN[MAXM],NEX[MAXM],LAS[MAXM],TOT;

void add(int x,int y){
	En[++Tot]=y;
	Nex[Tot]=Las[x];
	Las[x]=Tot;
}

void ADD(int x,int y){
	EN[++TOT]=y;
	NEX[TOT]=LAS[x];
	LAS[x]=TOT;
}

struct node{
	int s,t,l,r,len,id;
}ask[MAXN];int ask_tot;
bool operator<(node a,node b){
	return a.s>b.s;
}

void modify(int &p,int l,int r,int k){
	if(!p)p=++seg_tot;sz[p]++;
	if(l==r)return;
	int mid=l+r>>1;
	if(k<=mid)modify(ls[p],l,mid,k);
	else modify(rs[p],mid+1,r,k);
}

int Merge(int x,int y,int l,int r){
	if(!x||!y)return x|y;
	int p=++seg_tot,mid;
	if(l==r){
		sz[p]=sz[x]+sz[y];
		return p;
	}
	mid=l+r>>1;
	ls[p]=Merge(ls[x],ls[y],l,mid);
	rs[p]=Merge(rs[x],rs[y],mid+1,r);
	sz[p]=sz[ls[p]]+sz[rs[p]];
	return p;
}

int findnext(int p,int l,int r,int k){
	if(k>N||sz[p]==0)return -1;
	if(l==r)return k<=l?l:-1;
	int mid=l+r>>1,ret=-1;
	if(l>=k&&sz[ls[p]])return findnext(ls[p],l,mid,k);
	if(mid>=k){
		if(sz[ls[p]])ret=findnext(ls[p],l,mid,k);
		if(~ret)return ret;
		return findnext(rs[p],mid+1,r,k);
	}
	return findnext(rs[p],mid+1,r,k);
}

int push(int val){
	mx[++tot]=val;
	return tot;
}

void extend(int t){
	int p,q,np,nq;
	np=push(mx[las]+1);
	for(p=las;p&&!son[p][t];p=par[p][0])son[p][t]=np;
	if(!p)par[np][0]=srt;
	else{
		q=son[p][t];
		if(mx[q]==mx[p]+1)par[np][0]=q;
		else{
			nq=push(mx[p]+1);
			memcpy(son[nq],son[q],sizeof(son[q]));
			par[nq][0]=par[q][0];
			par[q][0]=par[np][0]=nq;
			for(;son[p][t]==q;p=par[p][0])son[p][t]=nq;
		}
	}
	las=np;
}

int jump(int p,int d){
	for(int i=19;i>=0;i--)if(mx[par[p][i]]>=d)p=par[p][i];
	return p;
}

void dfs(int x){
	int i,y;
	for(i=1;i<20;i++)par[x][i]=par[par[x][i-1]][i-1];
	for(i=Las[x];i;i=Nex[i]){
		y=En[i];
		dfs(y);
		rt[x]=Merge(rt[x],rt[y],1,seg_n);
	}
}

void sam_init(){
	int i;
	seg_n=N;
	for(i=2;i<=tot;i++)add(par[i][0],i);
	for(i=1;i<=N;i++)modify(rt[pos[i]],1,seg_n,i);
	dfs(1);
}

ll solve1(int s,int t,int l,int r){
	ll ret=0;int len=r-l+1,cur,p;
	p=jump(pos[N+1+r],len);
	cur=findnext(rt[p],1,seg_n,s+len-1);
	while(cur<=t&&cur!=-1){
		ret+=(ll)K-(cur-len+1);
		cur=findnext(rt[p],1,seg_n,cur+len);
	}
	return ret;
}

//part 1

ll gethash(ll h[],int l,int r){
	return h[r]-h[l-1]*pw[r-l+1];
}

void solve2(int x,int dep){
	int i,j,d,p,y,r;
	ll ret;
	for(j=0;j<save[x].size();j++){
		p=save[x][j];
		ret=0;d=dep;r=ask[p].t-ask[p].len+1;
		for(i=19;i>=0;i--)if((d>=(1<<i))&&ori_beg[D[d-(1<<i)]]<=r){
			ret+=sum[d]-sum[d-(1<<i)];
			d-=(1<<i);
		}
		if(ori_beg[D[d]]<=r&&d)ret+=sum[d]-sum[d-1];
		Ans[ask[p].id]=ret;
	}
	
	for(i=LAS[x];i;i=NEX[i]){
		y=EN[i];
		sum[dep+1]=sum[dep]+K-ori_beg[y];
		D[dep+1]=y;
		solve2(y,dep+1);
	}
}

//part 2

int main(){
	int i,j,k,s,t,l,r,tmp;
	ll hh;
	
	srt=las=push(0);
	scanf("%d%d",&N,&K);
	
	for(i=1,pw[0]=1;i<=N;i++)pw[i]=pw[i-1]*sd;
	scanf("%s",A+1);
	for(i=1;i<=N;i++)extend(A[i]-'a'),pos[i]=las;
	for(i=1;i<=N;i++)ha[i]=ha[i-1]*sd+A[i];
	extend(26);
	scanf("%s",A+1);
	for(i=1;i<=N;i++)extend(A[i]-'a'),pos[i+N+1]=las;
	for(i=1;i<=N;i++)hb[i]=hb[i-1]*sd+A[i];
	
	sam_init();
	
	scanf("%d",&Q);
	for(i=1;i<=Q;i++){
		scanf("%d%d%d%d",&s,&t,&l,&r);
		if(s+(r-l+1)>t)continue;
		if(r-l+1<=LIM){
			ask_tot++;
			ask[ask_tot]=(node){s,t,l,r,r-l+1,i};
			las_pos[gethash(hb,l,r)]=N+1;
		}
		else Ans[i]=solve1(s,t,l,r);
	}
	
	sort(ask+1,ask+ask_tot+1);
	for(i=1;i<=LIM;i++)nex[N+1][i]=N+1;
	j=N+1;
	
	for(i=1;i<=ask_tot;i++){
		while(j>ask[i].s){
			j--;
			for(k=1;k<=min(LIM,N-j+1);k++){
				hh=gethash(ha,j,j+k-1);
				if(!las_pos.count(hh))continue;
				id[j][k]=++id_tot;ori_beg[id_tot]=j;
				
				tmp=las_pos[hh];
				nex[j][k]=tmp;
				while(tmp<=j+k-1)tmp=nex[tmp][k];
				ADD(id[tmp][k],id[j][k]);
				las_pos[hh]=j;
			}
		}
		hh=gethash(hb,ask[i].l,ask[i].r);
		s=las_pos[hh];
		if(s+ask[i].len-1>ask[i].t)continue;
		save[id[s][ask[i].len]].push_back(i);
	}
	
	ori_beg[0]=N+1;
	solve2(0,0);
	
	for(i=1;i<=Q;i++)printf("%llu\n",Ans[i]);
}