2754: [SCOI2012]喵星球上的点名
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 2068 Solved: 907
[Submit][Status][Discuss]
Description
a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。 然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来表示喵星人的名字。
现在你能帮助a180285统计每次点名的时候有多少喵星人答到，以及M次点名结束后每个喵星人答到多少次吗？
Input
现在定义喵星球上的字符串给定方法：
先给出一个正整数L，表示字符串的长度，接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数N和M。
接下来有N行，每行包含第i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的
字符串。
接下来有M行，每行包含一个喵星球上的字符串，表示老师点名的串。
Output
对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。
Sample Input
2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25
Sample Output
2
1
0
1 2
【提示】
事实上样例给出的数据如果翻译成地球上的语言可以这样来看
2 3
izayoi sakuya
orihara izaya
izay
hara
raiz
1
0
1 2
【提示】
事实上样例给出的数据如果翻译成地球上的语言可以这样来看
2 3
izayoi sakuya
orihara izaya
izay
hara
raiz
HINT
【数据范围】
对于30%的数据，保证：
1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。
对于100%的数据，保证：
1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。
Solution1
把名字和点名串用不同的字符连在一起，给对应名字的后缀打标记，做出后缀数组后，对于每个询问，找出其rank值，在sa中左右两边找，用一个数组统计答案即可。
这个东西是很暴力的，但是，数据很水，就可以水过了。
打的时候，把x设了值，又把x、y换了，调了很久。
Solution2
上面的做法是比较不稳定的，看数据，下面的做法则是稳定的O(nlogn)-----(十分感谢Semiwaker大佬的指导)。
我们可以发现，对于一个询问，那么它在sa数组中对应了一段可行的区间，需要统计这个区间内有多少个属于不同名字的后缀。
另外，我们也需要知道，属于同一个名字的后缀，被多少个区间所覆盖。
对于第一个问题，我们可以利用扫描线的方法来解决。对于每个名字所对应的后缀，我们只去计算它最后的那一个。但这个要怎么搞呢？
我们可以把所有的区间按右端点为第一关键字，左端点为第二关键字排序。假设当前遇到了一个后缀，我们就看同名字的后缀前面有没有出现过，如果没有，就直接在该位置+1；否则就把前面出现过的最后的那个后缀的位置-1，再在当前位置上+1。这个可以用一个树状数组来维护，遇到询问区间，只需要区间求和就好。
对于第二个问题，我们依然可以利用扫描线的方法来解决。对于每个名字所对应的的后缀，我们只计算它在该询问区间中，出现的最左的那一个就好。
我们可以把所有区间化为左端点+1、右端点-1。那么要如何统计呢？我们记录每一个名字当前出现的最迟的后缀的编号，再做一个区间求和就可以了，这个可以用树状数组来完成。
总的时间复杂度为O(nlogn)，但似乎跑得比暴力还要慢，是我写得不好吗？
Code1
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <set> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define DWN(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define mset(a, b) memset(a, b, sizeof(a))
const int maxn = ;
int sa[maxn], h[maxn], rk[maxn], num[maxn];
int w_a[maxn], w_b[maxn], w_v[maxn], w_s[maxn];
int bel[maxn];
struct Node
{
int len, start;
}d[maxn];
int vis[maxn], ans[maxn];
int temp[maxn], t_cnt; bool cmp(int *x, int a, int b, int l)
{
return x[a+l] == x[b+l] && x[a] == x[b];
} void da(int n, int m)
{
int *x = w_a, *y = w_b, *t; t_cnt = ;
REP(i, , n) x[i] = num[i];
REP(i, , m) w_s[i] = ;
REP(i, , n) w_s[x[i]] ++;
REP(i, , m) w_s[i] += w_s[i-];
DWN(i, n, ) sa[w_s[x[i]] --] = i;
for (int j = , p = ; p != n; m = p, j *= )
{
p = ;
REP(i, n-j+, n)
y[++p] = i;
REP(i, , n)
if (sa[i]-j > )
y[++p] = sa[i]-j;
REP(i, , n) w_v[i] = x[y[i]];
REP(i, , m) w_s[i] = ;
REP(i, , n) w_s[w_v[i]] ++;
REP(i, , m) w_s[i] += w_s[i-];
DWN(i, n, ) sa[w_s[w_v[i]] --] = y[i];
p = , t = x, x = y, y = t, x[sa[]] = ; //千万注意啊，不能把交换往后挪啊
REP(i, , n) x[sa[i]] = cmp(y, sa[i], sa[i-], j) ? p : ++p;
}
} void calc_height(int n)
{
REP(i, , n) rk[sa[i]] = i;
int k = ;
REP(i, , n)
{
if (k) k --;
int j = sa[rk[i]-];
while (num[i+k] == num[j+k] && i+k <= n && j+k <= n) k ++;
h[rk[i]] = k;
}
} int main()
{
int len = , n, m, breaker = ;
scanf("%d %d", &n, &m);
REP(i, , n)
{
int l;
scanf("%d", &l);
REP(j, , l)
scanf("%d", &num[++len]), bel[len] = i, num[len] ++;
num[++len] = ++breaker;
scanf("%d", &l);
REP(j, , l)
scanf("%d", &num[++len]), bel[len] = i, num[len] ++;
num[++len] = ++breaker;
}
REP(i, , m)
{
scanf("%d", &d[i].len);
d[i].start = len+;
REP(j, , d[i].len)
scanf("%d", &num[++len]), num[len] ++;
num[++len] = ++breaker;
}
da(len, breaker);
calc_height(len);
REP(i, , m)
{
int l = rk[d[i].start], r = rk[d[i].start], now_l = d[i].len;
while (l >= && min(h[l], now_l) >= d[i].len)
now_l = min(now_l, h[l]), l --;
now_l = len;
while (r+ <= n && min(now_l, h[r+]) >= d[i].len)
r ++, now_l = min(now_l, h[r]);
int cnt = ;
REP(j, l, r)
if (vis[bel[sa[j]]] != i && bel[sa[j]] != )
{
vis[bel[sa[j]]] = i;
cnt ++;
ans[bel[sa[j]]] ++;
}
printf("%d\n", cnt);
}
REP(i, , n)
printf("%d%c", ans[i], i == n ? '\n' : ' ');
return ;
}
Code2
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define DWN(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define mset(a, b) memset(a, b, sizeof(a))
const int maxn = ;
int n, m, bel[maxn], num[maxn];
int w_a[maxn], w_b[maxn], w_v[maxn], w_s[maxn], sa[maxn], rk[maxn], h[maxn], st[maxn][];
struct Node
{
int len, start, l, r, id;
bool operator < (const Node &AI) const { return r == AI.r ? l < AI.l : r < AI.r; }
}query[maxn];
int c[maxn], las[maxn], ans1[maxn], ans2[maxn], add[maxn];
vector <int> del[maxn]; bool cmp(int *x, int a, int b, int l) { return x[a] == x[b] && x[a+l] == x[b+l]; } void get_sa(int n, int m)
{
int *x = w_a, *y = w_b, *t;
REP(i, , m) w_s[i] = ;
REP(i, , n) w_s[x[i]=num[i]] ++;
REP(i, , m) w_s[i] += w_s[i-];
DWN(i, n, ) sa[w_s[x[i]]--] = i;
for (int j = , p = ; p != n; j *= , m = p)
{
p = ;
REP(i, n-j+, n) y[++p] = i;
REP(i, , n) if (sa[i]-j > ) y[++p] = sa[i]-j;
REP(i, , n) w_v[i] = x[y[i]];
REP(i, , m) w_s[i] = ;
REP(i, , n) w_s[w_v[i]] ++;
REP(i, , m) w_s[i] += w_s[i-];
DWN(i, n, ) sa[w_s[w_v[i]]--] = y[i];
t = x, x = y, y = t, p = , x[sa[]] = ;
REP(i, , n) x[sa[i]] = cmp(y, sa[i], sa[i-], j) ? p : ++p;
}
} void get_h(int n)
{
REP(i, , n) rk[sa[i]] = i;
int k = ;
REP(i, , n)
{
if (k) k --;
int j = sa[rk[i]-];
while (num[i+k] == num[j+k] && i+k <= n && j+k <= n) k ++;
h[rk[i]] = k;
}
REP(i, , n) st[i][] = h[i];
REP(j, , )
REP(i, , n)
if (i+(<<(j-)) <= n)//必须判断，不然会RE
st[i][j] = min(st[i][j-], st[i+(<<(j-))][j-]);
} int calc(int l, int r)
{
l ++;
int k = int(log2(r-l+));
return min(st[l][k], st[r-(<<k)+][k]);
} int lowbit(int x) { return x & -x; } void c_modify(const int &n, int x, int d) { while (x <= n) c[x] += d, x += lowbit(x); } int c_query(const int &n, int x)
{
int ret = ;
while (x > ) ret += c[x], x -= lowbit(x);
return ret;
} int main()
{
scanf("%d %d", &n, &m);
int breaker = , len = ;
REP(i, , n)
{
int l;
scanf("%d", &l);
REP(j, , l) scanf("%d", &num[++len]), bel[len] = i, num[len] ++;
num[++len] = ++breaker;
scanf("%d", &l);
REP(j, , l) scanf("%d", &num[++len]), bel[len] = i, num[len] ++;
num[++len] = ++breaker;
}
REP(i, , m)
{
scanf("%d", &query[i].len), query[i].id = i;
query[i].start = len+;
REP(j, , query[i].len) scanf("%d", &num[++len]), num[len] ++;
num[++len] = ++breaker;
}
get_sa(len, breaker), get_h(len);
REP(i, , m)
{
int k = rk[query[i].start], l = , r = k;
query[i].l = query[i].r = k;
while (l <= r)
{
int mid = (l+r)>>;
if (calc(mid, k) >= query[i].len) query[i].l = mid, r = mid-;
else l = mid+;
}
l = k+, r = len;
while (l <= r)
{
int mid = (l+r)>>;
if (calc(k, mid) >= query[i].len) query[i].r = mid, l = mid+;
else r = mid-;
}
}
sort(query+, query+m+);
int now = ;
REP(i, , len)
{
int k = sa[i];
if (bel[k] != )
{
if (las[bel[k]] != ) c_modify(len, las[bel[k]], -);
las[bel[k]] = i, c_modify(len, i, );
}
while (query[now].r == i && now <= m)
ans1[query[now].id] = c_query(len, i)-c_query(len, query[now].l-), now ++;
}
mset(c, ), mset(las, );
REP(i, , m) add[query[i].l] ++, del[query[i].r+].push_back(query[i].l);
REP(i, , len)
{
int k = sa[i];
c_modify(len, i, add[i]);
REP(j, , del[i].size()-) c_modify(len, del[i][j], -);//这段尤为注意，必须一边做一边删
//否则，就会出现减出负数的情况
if (bel[k] != )
{
if (las[bel[k]] != ) ans2[bel[k]] -= c_query(len, las[bel[k]]);
ans2[bel[k]] += c_query(len, i), las[bel[k]] = i;
}
}
REP(i, , m) printf("%d\n", ans1[i]);
REP(i, , n) printf("%d%c", ans2[i], i == n ? '\n' : ' ');
return ;
}