洛谷 P2336 [SCOI2012]喵星球上的点名

题目描述

a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有 N 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。

然而，由于喵星人的字码过于古怪，以至于不能用 ASCII 码来表示。为了方便描述，a180285 决定用数串来表示喵星人的名字。

现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到，以及 M 次点名结束后每个喵星人答到多少次吗？

输入输出格式

输入格式：

现在定义喵星球上的字符串给定方法：

先给出一个正整数 L ，表示字符串的长度，接下来L个整数表示字符串的每个字符。

输入的第一行是两个整数 N 和 M。

接下来有 N 行，每行包含第 i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的字符串。

接下来有 M 行，每行包含一个喵星球上的字符串，表示老师点名的串。

输出格式：

对于每个老师点名的串输出有多少个喵星人应该答到。

然后在最后一行输出每个喵星人被点到多少次。

输入输出样例

输入样例#1：

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

输出样例#1：

说明

事实上样例给出的数据如果翻译成地球上的语言可以这样来看

2 3

izayoi sakuya

orihara izaya

izay hara raiz

对于 30%的数据，保证：

1<=N,M<=1000,喵星人的名字总长不超过 4000，点名串的总长不超过 2000，

对于 100%的数据，保证：

1<=N<=20000 ，1<=M<=50000. 喵星人的名字总长和点名串的总长分别不超过100000,保证喵星人的字符串中作为字符存在的数不超过 10000

题目大意：多个模板串多个匹配串，求每个模板串被匹配了多少次，每个匹配串匹配了多少模板，字符集很大

要命题，调了一下午

AC自动机的最坏复杂度是n^2，然而这题没有卡，可以过

后缀数组+ST表+二分+莫队+差分

首先把这么一大堆东西串起来，像这样

izayoi#sakuya#orihara#izaya#izay#hara#raiz#

具体实现的话所有字符+1，0充当分隔符就好了

然后对每一个名字所占据的位置记录一下颜色，像这样

izayoi#sakuya#orihara#izaya#izay#hara#raiz#
1111111111111122222222222222000000000000000

记录一下每一个点名的起点和长度

然后把sa和height求出来

先搞定每个匹配串匹配多少模板，把height的ST表搞出来，二分一下height>点名长度的区间，这个区间的中间位置大概在rank[点名起点]，但也可能是个空区间，需要特判一下

然后就问题变成了区间颜色个数，莫队模板题

然后处理每个模板串被多少匹配串匹配过

做一个差分，每次在莫队添加和删除元素的时候，如果把一种颜色删光了，给这种颜色的出现次数减去剩下的询问数量，如果一种颜色新出现了，加上剩下的询问数量

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <string>
  6 #include <cstring>
  7 #include <cmath>
  8 #include <map>
  9 #include <stack>
 10 #include <set>
 11 #include <vector>
 12 #include <queue>
 13 #include <time.h>
 14 #define eps 1e-7
 15 #define INF 0x3f3f3f3f
 16 #define MOD 1000000007
 17 #define rep0(j,n) for(int j=0;j<n;++j)
 18 #define rep1(j,n) for(int j=1;j<=n;++j)
 19 #define pb push_back
 20 #define mp make_pair
 21 #define set0(n) memset(n,0,sizeof(n))
 22 #define ll long long
 23 #define ull unsigned long long
 24 #define iter(i,v) for(edge *i=head[v];i;i=i->nxt)
 25 #define max(a,b) (((a)>(b))?(a):(b))
 26 #define min(a,b) (((a)<(b))?(a):(b))
 27 #define print_runtime printf("Running time:%.3lfs
",double(clock())/1000.0)
 28 #define TO(j) printf(#j": %d
",j);
 29 //#define OJ
 30 using namespace std;
 31 const int MAXINT = 401000;
 32 const int MAXNODE = 100010;
 33 const int MAXEDGE = 2 * MAXNODE;
 34 char BUF, *buf;
 35 int read() {
 36     char c = getchar(); int f = 1, x = 0;
 37     while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
 38     while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
 39     return f * x;
 40 }
 41 char get_ch() {
 42     char c = getchar();
 43     while (!isalpha(c)) c = getchar();
 44     return c;
 45 }
 46 //------------------- Head Files ----------------------//
 47 int cnt_qr, sa[MAXINT], rk[MAXINT], trk[MAXINT], height[MAXINT], tsa[MAXINT], tstr[MAXINT], cnt[MAXINT], len, s[MAXINT], n, m, color[MAXINT];
 48 int st[18][MAXINT], maxp[MAXINT*2], ans=0, cnt_c[50010], cnt_miao[20010], rp;
 49 pair<int, int> qr[50010];
 50 struct query {
 51     int l, r, id;
 52     query() {}
 53     query(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {}
 54 } mo[MAXINT];
 55 bool operator < (const query &a, const query &b) {
 56     return (a.l / 447 == b.l / 447) ? a.r < b.r : (a.l / 447 < b.l / 447);
 57 }
 58 int cmp(int *a, int p1, int p2, int l) {
 59     return a[p1] == a[p2] && a[p1 + l] == a[p2 + l];
 60 }
 61 void get_st() {
 62     rep0(i, 18) {
 63         for (int j = (1 << i); j < (1 << (i + 1)); j++) maxp[j] = i;
 64     }
 65     rep0(i, len) st[0][i] = height[i];
 66     rep1(i, 17) rep0(j, len - (1 << i) + 1) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
 67 }
 68 int gt(int l, int r) { //[l,r]
 69     int pw = maxp[r - l + 1];
 70     return min(st[pw][l], st[pw][r - (1 << pw) + 1]);
 71 }
 72 void get_sa() {
 73     int i, j, k, sz = MAXINT;
 74     for (i = 0; i < sz; i++) cnt[i] = 0;
 75     for (i = 0; i < len; i++) cnt[trk[i] = s[i]]++;
 76     for (i = 1; i < sz; i++) cnt[i] += cnt[i - 1];
 77     for (i = len - 1; i >= 0; i--) sa[--cnt[s[i]]] = i;
 78     for (j = 1, k = 1; k < len; j <<= 1, sz = k) {
 79         for (k = 0, i = len - j; i < len; i++) tsa[k++] = i;
 80         for (i = 0; i < len; i++) if (sa[i] >= j) tsa[k++] = sa[i] - j;
 81         for (i = 0; i < len; i++) tstr[i] = trk[tsa[i]];
 82 
 83         for (i = 0; i < sz; i++) cnt[i] = 0;
 84         for (i = 0; i < len; i++) cnt[tstr[i]]++;
 85         for (i = 1; i < sz; i++) cnt[i] += cnt[i - 1];
 86         for (i = len - 1; i >= 0; i--) sa[--cnt[tstr[i]]] = tsa[i];
 87         for (swap(tsa, trk), k = 1, trk[sa[0]] = 0, i = 1; i < len; i++) {
 88             trk[sa[i]] = cmp(tsa, sa[i], sa[i - 1], j) ? k - 1 : k++;
 89         }
 90     }
 91 }
 92 void get_height() {
 93     int i, j, k;
 94     for (i = 0; i < len; i++) rk[sa[i]] = i;
 95     for (i = 0, k = 0; i < len - 1; height[rk[i++]] = k) {
 96         for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
 97     }
 98 }
 99 query get_query(int id) {
100     int pos = rk[qr[id].first], l = qr[id].second;
101     query ret; ret.id = id;
102     if (pos == len - 1) pos = pos + 1;
103     else {
104         if (height[pos] < l) pos = pos + 1;
105     }
106     if (height[pos] < l) return query(-1, -1, -1);
107     int mid, lb = pos, rb = len;
108     while (rb - lb > 1) {
109         mid = (lb + rb) / 2;
110         if (gt(pos, mid) < l) rb = mid; else lb = mid;
111     }
112     ret.r = lb;
113     lb = 0; rb = pos;
114     while (rb - lb > 1) {
115         mid = (lb + rb) / 2;
116         if (gt(mid, pos) < l) lb = mid; else rb = mid;
117     }
118     ret.l = rb - 1;
119     return ret;
120 }
121 void get_input();
122 void work();
123 void append() {
124     int l = read();
125     rep0(i, l) {
126         int w = read();
127         s[len++] = w + 1;
128     }
129     s[len++] = 0;
130 }
131 void add(int v) {
132     cnt[v]++;
133     if (v != 0 && cnt[v] == 1) {
134         ans++;
135         cnt_miao[v] += cnt_qr - rp;
136     }
137 }
138 void del(int v) {
139     cnt[v]--;
140     if (v!=0 && cnt[v] == 0) {
141         ans--;
142         cnt_miao[v] -= cnt_qr - rp;
143     };
144 }
145 int main() {
146     get_input();
147     work();
148     return 0;
149 }
150 void work() {
151     get_sa();
152     get_height();
153     get_st();
154     rep0(i, m) {
155         mo[cnt_qr] = get_query(i);
156         if (mo[cnt_qr].id != -1) cnt_qr++;
157     }
158     sort(mo, mo + cnt_qr);
159     memset(cnt, 0, sizeof(cnt));
160     int l = 0, r = -1;
161     for (rp = 0; rp < cnt_qr; rp++) {
162         for (; l < mo[rp].l; del(color[sa[l]]), l++);
163         for (; l > mo[rp].l; l--, add(color[sa[l]]));
164         for (; r > mo[rp].r; del(color[sa[r]]), r--);
165         for (; r < mo[rp].r; r++, add(color[sa[r]]));
166         cnt_c[mo[rp].id] = ans; l = mo[rp].l; r = mo[rp].r;
167     }
168     rep0(i, m) printf("%d
", cnt_c[i]);
169     rep1(i, n) printf("%d ", cnt_miao[i]);
170     putchar('
');
171 }
172 void get_input() {
173     n = read(); m = read();
174     int l;
175     rep1(i, n) {
176         int p = len;
177         append(); append();
178         for (int j = p; j < len; j++) color[j] = i;
179     }
180     rep0(i, m) {
181         int p = len;
182         append();
183         for (int j = p; j < len; j++) color[j] = 0;
184         qr[i] = make_pair(p, len - p - 1);
185     }
186 }
187 /*
188 2 1
189 2 2 1 1 1
190 2 2 1 1 1
191 2 2 1
192 */