题解 P5270 【无论怎样神树大人都会删库跑路】
龙之吻—水货
2019-03-24 15:29:32
# 无论怎样神树大人都会删库跑路
## 题目大意
中文题面自己去读吧 QwQ
## 一句话题解
Hash + 双端队列模拟。
## 解题报告
这道题，首先比较显然的一点是 : 只有字符串 $x$ 长度为 $T$ 的后缀是可能产生贡献的。
所以只需要去维护 $x$ 的后 $T$ 位中，每种数字出现的个数。同时考虑到前 $60pts$ 的字符集都特别小。我们完全可以使用双端队列 $+$ 桶来模拟这个过程。
也就是每次从尾部加入字符，从头部删除字符。
```cpp
for (register int i = 1; i <= q; i++) {
int now = r[i % m + 1];
for (register int j = 1; j <= len[now]; j++) {
qu.push(a[now][j]);
tot[a[now][j]]++;
}
while (qu.size() > (unsigned)t) {
tot[qu.front()]--;
qu.pop();
}
}
```
这样就有 $20pts$ 了！
但是，显然，对于 $Q$ 比较大的情况，上述方法并不适用。
但是我们发现每次操作是每 $m$ 个一循环的，所以当 $x$ 的长度大于 $T$ 的时候，进行第 $i$ 操作和进行第 $i+m$ 次操作对答案的贡献是一样的。
这样我们就可以先进行几轮操作使得 $x$ 的长度大于 $T$，然后在进行一轮操作求出 $sum[i]$ 表示从第 $1$ 个操作到第 $i$ 个操作中有多少个操作对答案产生了贡献。
同时，我们还发现，对于前 $60pts$，有 $R_i = i$，因此插入的字符个数是 $O(字符串总长)$ 级别的。
相比之前的 $20pts$ 做法只多了几句话。
```cpp
for (register int i = 1; i <= m; i++) {
int now = r[i];
for (register int j = 1; j <= len[now]; j++) {
qu.push(a[now][j]);
tot[a[now][j]]++;
}
while (qu.size() > (unsigned)t) {
tot[qu.front()]--;
qu.pop();
}
res[i] = res[i - 1] + check();
}
ans += res[m] * (q / m);
ans += res[q % m];
```
现在我们考虑满分做法，从 $60pts$ 到满分有两个问题，首先是字符集大小变成了 $10^5$ 这样的话每次判断的复杂度过高；然后是插入的字符串没有保证，可能连续 $m$ 次都要求插入同一个长度为 $10^5$ 的字符串，复杂度依然爆炸。。。
先尝试解决第一个问题，显然 $hash$ 是解决第一个问题比较好的方法之一。
这里我们使用最普通的 $hash$，也就是 $hash_s = \sum_{i=0}s[i] \times base^i$，至于是自然溢出，单模数，双模数，还是 $n$ 模数不作介绍。
把用于储存数字的桶当成一个字符串 $hash$ 掉，在这里我们会用到 $hash$ 的一个性质，我们用一个字符串的 $hash$ 值减去另一个字符串的 $hash$ 会得到两个字符串按位相减的到的字符串的 $hash$ 值， 相加同理。
举个栗子就是 ：
$hash(234576) - hash(123456) = hash(111120)$
$hash(1111) + hash(1234) = hash(2345)$
当然，需要保证第一个字符串的每一位都大于第二个字符串的相应位置，以及要保证加出来的数小于 $base$ 。
利用这个性质，还可以得出来 :
$hash(123456) + base^2 = hash(124456)$ 。
这样，就可以在 $O(1)$ 的时间内加入一个字符，删除一个字符，检查贡献。
同时，还发现如果我们预处理出来 $n$ 个小字符串的 $hash$ 值，那么就可以在 $O(1)$ 的时间内加入一个字符串，删除一个字符串。
那么，可以在双端队列里面存储一个字符串而不是单个字符。
至于从双端队列头部删除，会有两种情况 :
- 整个字符串都需要删掉，那么直接弹出并减去即可。
- 字符串需要删掉一部分，考虑到在队列中储存的字符串要么是一个整串，要么是一个后缀，只需要预处理出 $n$ 的给定的字符串的所有后缀的值，删去一个后缀再从头部加入一个后缀即可 (实际上就是删除一个子串)。
经过简单的分析，复杂度是 $O(n)$ 的。
附上代码 :
```cpp
#include<cstdio>
#include<algorithm>
#include<deque>
typedef unsigned long long ull;
typedef std::pair<ull, ull> par;
const int maxn = 1e5 + 7;
const int base = 1e5 + 7;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
ull pow1[maxn], pow2[maxn];
par operator + (const par &x, const par &y) {
par res = x;
res.first = (res.first + y.first) % mod1;
res.second = (res.second + y.second) % mod2;
return res;
}
par operator - (const par &x, const par &y) {
par res = x;
res.first = (res.first + mod1 - y.first) % mod1;
res.second = (res.second + mod2 - y.second) % mod2;
return res;
}
class Solution{
private :
struct Node{
int id, len;
Node(int id, int len) :
id(id), len(len) {}
};
int n, t, q, s[maxn], len[maxn], *a[maxn], m, r[maxn], res[maxn];
par hashS, *hashA[maxn], hashNow;
int lenth, ans;
std::deque<Node> dq;
void init() {
pow1[0] = pow2[0] = 1;
for (register int i = 1; i <= 100000; i++) {
pow1[i] = pow1[i - 1] * base % mod1;
pow2[i] = pow2[i - 1] * base % mod2;
}
}
par getHash(int id, int l, int r) {
ull res1 = (hashA[id][r].first + mod1 - hashA[id][l - 1].first) % mod1;
ull res2 = (hashA[id][r].second + mod2 - hashA[id][l - 1].second) % mod2;
return std::make_pair(res1, res2);
}
par getSuc(int id, int lenth) {
return getHash(id, len[id] - lenth + 1, len[id]);
}
public :
Solution() {
init();
get();
solve();
}
void get() {
scanf("%d %d %d", &n, &t, &q);
for (register int i = 1; i <= t; i++) {
scanf("%d", s + i);
hashS.first = (hashS.first + pow1[s[i]]) % mod1;
hashS.second = (hashS.second + pow2[s[i]]) % mod2;
}
for (register int i = 1; i <= n; i++) {
scanf("%d", len + i);
a[i] = new int[len[i] + 1];
hashA[i] = new par[len[i] + 1];
hashA[i][0] = std::make_pair(0u, 0u);
for (register int j = 1; j <= len[i]; j++) {
scanf("%d", a[i] + j);
hashA[i][j].first = (hashA[i][j - 1].first + pow1[a[i][j]]) % mod1;
hashA[i][j].second = (hashA[i][j - 1].second + pow2[a[i][j]]) % mod2;
}
}
scanf("%d", &m);
for (register int i = 1; i <= m; i++) {
scanf("%d", r + i);
}
}
void solve() {
if (q <= m) {
for (register int i = 1; i <= q; i++) {
int now = r[i];
hashNow = hashNow + hashA[now][len[now]];
lenth += len[now];
dq.push_back(Node(now, len[now]));
while (lenth > t) {
Node nd = dq.front();
dq.pop_front();
if (lenth - nd.len >= t) {
hashNow = hashNow - getSuc(nd.id, nd.len);
lenth -= nd.len;
} else {
int del = lenth - t;
dq.push_front(Node(nd.id, nd.len - del));
lenth -= del;
hashNow = hashNow - getSuc(nd.id, nd.len);
hashNow = hashNow + getSuc(nd.id, nd.len - del);
}
}
if (hashNow == hashS) {
ans++;
}
}
printf("%d\n", ans);
return;
}
for (register int i = 1; i <= m; i++) {
int now = r[i];
hashNow = hashNow + hashA[now][len[now]];
//printf("%d\n", len[now]);
lenth += len[now];
dq.push_back(Node(now, len[now]));
while (lenth > t) {
Node nd = dq.front();
dq.pop_front();
if (lenth - nd.len >= t) {
hashNow = hashNow - getSuc(nd.id, nd.len);
lenth -= nd.len;
} else {
int del = lenth - t;
dq.push_front(Node(nd.id, nd.len - del));
lenth -= del;
hashNow = hashNow - getSuc(nd.id, nd.len);
hashNow = hashNow + getSuc(nd.id, nd.len - del);
}
}
//printf("%d : %llu %llu\n", i, hashNow.first, hashNow.second);
//printf("%d %d\n", i, lenth);
if (hashNow == hashS) {
ans++;
}
}
q -= m;
for (register int i = 1; i <= m; i++) {
int now = r[i];
hashNow = hashNow + hashA[now][len[now]];
lenth += len[now];
dq.push_back(Node(now, len[now]));
while (lenth > t) {
Node nd = dq.front();
dq.pop_front();
if (lenth - nd.len >= t) {
hashNow = hashNow - getSuc(nd.id, nd.len);
lenth -= nd.len;
} else {
int del = lenth - t;
dq.push_front(Node(nd.id, nd.len - del));
lenth -= del;
hashNow = hashNow - getSuc(nd.id, nd.len);
hashNow = hashNow + getSuc(nd.id, nd.len - del);
}
}
res[i] = res[i - 1] + (hashNow == hashS);
}
ans += res[m] * (q / m);
ans += res[q % m];
printf("%d\n", ans);
}
};
Solution sol;
int main() {}
```
ps : 尽管比赛的时候这份代码通过了所有的测试点，但是由于偷懒，它可能会被一些精心构造的数据卡掉，比如说某些进行 $m$ 次操作后得到的字符串 $x$ 的长度依然小于 $T$ 的数据。