BZOJ 2754
题意:见上。
考虑将所有名字姓和名用特殊符号链接,然后构造后缀数组
引理1:
$S_2$ 是 $S_1$ 的子串当且仅当 $\exists S_1$的后缀和$S_2$的$height=len(S_2)$
引理2:
后缀数组的$SA$数组具有二分单调性,即确定了前$i-1$位,可以在$SA$数组中二分第$i$位的位置
用引理1或者引理2(代码使用2)用上二分可以找出一个询问在$SA$数组上的区间范围,即这个区间上的后缀的前缀都有这个询问串。
这里二分要用左闭右闭区间的,用左闭右开会莫名GG
那么现在问题转化为求区间的不同颜色的个数,显然莫队裸题。
第二问的话,在莫队的时候,如果第一次加入某种颜色,则加上当前最大可能的个数,然后某种颜色被完全删除后就减掉当前最大可能的个数
知识点
1、二分
2、后缀数组从1开始
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200000 + 5;
int n, m, lmt, which[MAXN], tmp1, tmp2;
int a[MAXN], bl[MAXN], blolen;
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
int ans1[MAXN], ans2[MAXN];
struct qry {
int l, r, id;
bool operator < (const qry &rhs) const {
return bl[l] != bl[rhs.l] ? r < rhs.r : bl[l] < bl[rhs.l];
}
} xw[MAXN];
void build() {
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i; --i) SA[tax[rk[i]]--] = i;
for (int k = 1; k <= n; k *= 2) {
int p = 0;
for (int i = n - k + 1; i <= n; ++i) tp[++p] = i;
for (int i = 1; i <= n; ++i) if (SA[i] > k) tp[++p] = SA[i] - k;
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i; --i) SA[tax[rk[tp[i]]]--] = tp[i];
swap(rk, tp), p = 1, rk[SA[1]] = 1;
for (int i = 2; i <= n; ++i) {
rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
}
if (p >= n) break ;
m = p;
}
}
int l, r, cnt, tax_md[MAXN];
void inc(int pos, int whw) {
if (++tax_md[which[SA[pos]]] == 1) {
++cnt, ans2[which[SA[pos]]] += tmp2 - whw + 1;
}
}
void dec(int pos, int whw) {
if (--tax_md[which[SA[pos]]] == 0) {
--cnt, ans2[which[SA[pos]]] -= tmp2 - whw + 1;
}
}
void clean() {
n = 0, lmt = 10000 + 2, m = 10000 + 2;
ms(ans1, 0), ms(ans2, 0);
}
int solve() {
clean();
scanf("%d%d", &tmp1, &tmp2);
for (int len, i = 1; i <= tmp1; ++i) {
scanf("%d", &len);
for (int x, j = 1; j <= len; ++j) {
scanf("%d", &x);
a[++n] = x, which[n] = i;
}
a[++n] = lmt;
scanf("%d", &len);
for (int x, j = 1; j <= len; ++j) {
scanf("%d", &x);
a[++n] = x, which[n] = i;
}
a[++n] = lmt;
}
build();
blolen = sqrt(n);
for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blolen + 1;
for (int len, i = 1; i <= tmp2; ++i) { // 在 SA 数组中二分
scanf("%d", &len);
int L = 1, R = n;
for (int x, j = 1; j <= len; ++j) { // 找加入第 i 位后符合的下界
scanf("%d", &x);
int l = L, r = R, ltmp;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[SA[mid] + j - 1] < x) l = mid + 1; else r = mid - 1;
}
ltmp = l;
l = L, r = R;
while (l <= r) { // 找加入第 i 位后符合的上界
int mid = (l + r) >> 1;
if (a[SA[mid] + j - 1] <= x) l = mid + 1; else r = mid - 1;
}
L = ltmp, R = r;
}
if (L <= R) xw[i] = (qry){L, R, i};
}
sort(xw + 1, xw + 1 + tmp2);
l = 1, r = 0, cnt = 0;
for (int i = 1; i <= tmp2; ++i) {
while (l > xw[i].l) inc(l - 1, i), --l;
while (r < xw[i].r) inc(r + 1, i), ++r;
while (l < xw[i].l) dec(l, i), ++l;
while (r > xw[i].r) dec(r, i), --r;
ans1[xw[i].id] = cnt;
}
for (int i = 1; i <= tmp2; ++i) printf("%d\n", ans1[i]);
for (int i = 1; i <= tmp1; ++i) printf("%d ", ans2[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
test 1
2 1
3
1 2 1
3
1 2 1
3
1 2 2
3
1 2 2
3
1 2 1
test 2
2 1
3
1 2 0
3
1 2 0
3
1 2 0
3
1 2 0
3
1 2 1
*/