传送门

原本的想法是把所有的串不管是名字还是询问都连起来,记录一下询问串在sa数组中的位置

对于每个询问可以在sa数组中二分出左右边界,第一问用莫队,第二问差分乱搞。

结果发现我差分的思路想错了,先写了一个暴力,二分出左右边界之后直接从l枚举到r,想试试正确性,就交了一遍,结果过了。。。。

因为是暴力,可以不用二分左右边界,直接向左向右枚举扩展就可以了,st表也不用了,但我懒得改了

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 2000001 using namespace std; int n, m, cnt, mx, len;
int M[N], x[N], y[N], s[N], sa[N], b[N], d[N][21], Rank[N], Log[N], height[N], id[N], pos[N], ans[N], num[N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void build_sa()
{
int i, k, p;
for(i = 0; i < mx; i++) b[i] = 0;
for(i = 0; i < len; i++) b[x[i] = s[i]]++;
for(i = 1; i < mx; i++) b[i] += b[i - 1];
for(i = len - 1; i >= 0; i--) sa[--b[x[i]]] = i;
for(k = 1; k <= len; k <<= 1)
{
p = 0;
for(i = len - k; i < len; i++) y[p++] = i;
for(i = 0; i < len; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = 0; i < mx; i++) b[i] = 0;
for(i = 0; i < len; i++) b[x[y[i]]]++;
for(i = 1; i < mx; i++) b[i] += b[i - 1];
for(i = len - 1; i >= 0; i--) sa[--b[x[y[i]]]] = y[i];
swap(x, y);
p = 1, x[sa[0]] = 0;
for(i = 1; i < len; i++)
x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
if(p >= len) break;
mx = p;
}
} inline void build_height()
{
int i, j, k = 0;
for(i = 0; i < len; i++) Rank[sa[i]] = i;
for(i = 0; i < len; i++)
{
if(k) k--;
j = sa[Rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
} inline void build_st()
{
int i, j;
for(i = 1; i < len; i++)
{
Log[i] = log2(i);
d[i][0] = height[i];
}
Log[i] = log2(i);
for(j = 1; (1 << j) < len; j++)
for(i = 1; i + (1 << j) - 1 < len; i++)
d[i][j] = min(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);
} inline int query(int l, int r)
{
int t = Log[r - l + 1];
return min(d[l][t], d[r - (1 << t) + 1][t]);
} inline int search2(int p, int llen)
{
int r = p, l = 1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(query(mid, p) >= llen) r = mid - 1;
else l = mid + 1;
}
return r;
} inline int search1(int p, int llen)
{
p++;
int l = p, r = len - 1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(query(p, mid) >= llen) l = mid + 1;
else r = mid - 1;
}
return l - 1;
} inline void solve()
{
int i, j, l, r;
for(i = 1; i <= m; i++)
{
r = j = search1(Rank[id[i]], M[i]);
l = j = search2(Rank[id[i]], M[i]);
for(j = l; j <= r; j++)
if(!num[pos[sa[j]]]++ && pos[sa[j]]) cnt++, ans[pos[sa[j]]]++;
printf("%d\n", cnt);
cnt = 0;
for(j = l; j <= r; j++) num[pos[sa[j]]] = 0;
}
for(i = 1; i <= n; i++) printf("%d ", ans[i]);
} int main()
{
int i, j, t;
n = read();
m = read();
for(i = 1; i <= n; i++)
for(j = 1; j <= 2; j++)
{
t = read();
while(t--)
{
pos[len] = i;
s[len++] = read() + 100000;
}
s[len++] = mx++;
}
for(i = 1; i <= m; i++)
{
M[i] = read();
id[i] = len;
for(j = 1; j <= M[i]; j++) s[len++] = read() + 100000;
s[len++] = mx++;
}
mx = 120000;
build_sa();
build_height();
build_st();
solve();
return 0;
}

  

最新文章

  1. Struts2框架简介和示例
  2. 【Visual Lisp】块专题
  3. php文章内容分页并生成相应的htm静态页面代码
  4. 三分 --- ZOJ 3203 Light Bulb
  5. 使用Code First 创建数据库
  6. Discuz使用tools修复数据文件后,访问URL多出/source/plugin/tools,导致文章栏目无法访问
  7. LINQ to Entities 查询注意事项
  8. Chrome浏览器允许跨域请求配置
  9. 高级子查询【weber出品必属精品】
  10. 物理卷操作命令:pvcreate,pvscan,pvdisplay.卷组操作命令:vgcreate,vgdisplay. (转)
  11. 关于overfit的随笔
  12. mysql用户创建授权
  13. 2018-07-10 为Chrome和火狐浏览器编写扩展
  14. NOIP2013提高组 T2 火柴排队
  15. win10安装mysql5.7.20解压版
  16. Openrasp源码分析
  17. Linux的内存机制(转载)
  18. Shell文本操作-5
  19. An entry point cannot be marked with the &#39;async&#39; modifier
  20. (转)Putty server refused our key的三种原因和解决方法

热门文章

  1. 贪心水题。UVA 11636 Hello World,LA 3602 DNA Consensus String,UVA 10970 Big Chocolate,UVA 10340 All in All,UVA 11039 Building Designing
  2. groupmod - 修 改 群 组
  3. python 列表 字典转json
  4. jvm | 基于栈的解释器执行过程
  5. sort 与 sorted 区别:
  6. bootstrap 超大屏幕(Jumbotron)
  7. HTML5&lt;article&gt;元素
  8. 01_13_Struts_默认Action
  9. Apache超时配置
  10. java解析多层嵌套json字符串