【LG4070】[SDOI2016]生成魔咒

时间:2022-09-07 22:04:46

【LG4070】[SDOI2016]生成魔咒

题面

洛谷

题解

如果我们不用在线输的话,那么答案就是对于所有状态\(i\)

\[\sum (i.len-i.fa.len)
\]

现在我们需要在线询问,那么因为\(SAM\)是在线算法,我们考虑每次的对答案的贡献。

那么产生的贡献就是\(last.len-last.fa.len\)。

与\(yyb\)的对话:

Q:为什么构建自动机时中间过程新加的点不会算到最后答案中呢?

A:不影响答案啊,你在两个len之间断开,对于答案的贡献不变。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
struct Node {
unordered_map<int, int> ch;
int len, fa;
} t[MAX_N << 1];
int tot = 1, lst = 1;
long long ans = 0;
void extend(int c) {
int New = ++tot;
t[lst].ch[c] = New;
t[New].len = t[lst].len + 1;
int p = t[lst].fa; lst = tot;
while (p && t[p].ch.find(c) == t[p].ch.end()) t[p].ch[c] = New, p = t[p].fa;
if (!p) t[New].fa = 1;
else {
int q = t[p].ch[c];
if (t[q].len == t[p].len + 1) t[New].fa = q;
else {
int _q = ++tot; t[_q] = t[q];
t[New].fa = t[q].fa = _q, t[_q].len = t[p].len + 1;
while (p) {
unordered_map<int, int> :: iterator ite;
ite = t[p].ch.find(c);
if (ite == t[p].ch.end() || ite->second != q) break;
t[p].ch[c] = _q;
p = t[p].fa;
}
}
}
ans += t[New].len - t[t[New].fa].len;
} int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
int N = gi();
for (int i = 1; i <= N; i++) extend(gi()), printf("%lld\n", ans);
return 0;
}

【LG4070】[SDOI2016]生成魔咒的更多相关文章

  1. BZOJ4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒 后缀自动机

    #include<iostream> #include<cstdio> #include<cstring> #include<queue> #inclu ...

  2. BZOJ 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒 &lbrack;后缀自动机&rsqb;

    4516: [Sdoi2016]生成魔咒 题意:询问一个字符串每个前缀有多少不同的子串 做了一下SDOI2016R1D2,题好水啊随便AK 强行开map上SAM 每个状态的贡献就是\(Max(s)-M ...

  3. BZOJ&lowbar;4516&lowbar;&lbrack;Sdoi2016&rsqb;生成魔咒&lowbar;后缀数组&plus;ST表&plus;splay

    BZOJ_4516_[Sdoi2016]生成魔咒_后缀数组+ST表+splay Description 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 1.2 拼凑起来形成一个魔 ...

  4. P4070 &lbrack;SDOI2016&rsqb;生成魔咒

    题目地址:P4070 [SDOI2016]生成魔咒 相信看到题目之后很多人跟我的思路是一样的-- 肯定要用 SA(P3809 [模板]后缀排序) 肯定要会求本质不同的子串个数(P2408 不同子串个数 ...

  5. bzoj4516 &sol; P4070 &lbrack;SDOI2016&rsqb;生成魔咒

    P4070 [SDOI2016]生成魔咒 后缀自动机 每插入一个字符,对答案的贡献为$len[last]-len[fa[last]]$ 插入字符范围过大,所以使用$map$存储. (去掉第35行就是裸 ...

  6. 洛谷 P4070 &lbrack;SDOI2016&rsqb;生成魔咒 解题报告

    P4070 [SDOI2016]生成魔咒 题目描述 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 \(1\).\(2\) 拼凑起来形成一个魔咒串 \([1,2]\). 一个魔咒 ...

  7. &lbrack;Sdoi2016&rsqb;生成魔咒&lbrack;SAM or SA&rsqb;

    4516: [Sdoi2016]生成魔咒 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1017  Solved: 569[Submit][Statu ...

  8. 4516&colon; &lbrack;Sdoi2016&rsqb;生成魔咒

    4516: [Sdoi2016]生成魔咒 链接 题意: 求本质不同的子串. 分析: 后缀数组或者SAM都可以. 考虑SAM中每个点的可以表示的子串是一个区间min(S)~max(S),把每个点的这个区 ...

  9. &lbrack;SDOI2016&rsqb; 生成魔咒 - 后缀数组&comma;平衡树&comma;STL&comma;时间倒流

    [SDOI2016] 生成魔咒 Description 初态串为空,每次在末尾追加一个字符,动态维护本质不同的子串数. Solution 考虑时间倒流,并将串反转,则变为每次从开头删掉一个字符,即每次 ...

随机推荐

  1. HDU 5652 India and China Origins(经典并查集)

    特别经典的一个题,还有一种方法就是二分+bfs 题意:空间内n*m个点,每个点是0或者1,0代表此点可以走,1代表不能走.接着经过q年,每年一个坐标表示此点不能走.问哪年开始图上不能出现最上边不能到达 ...

  2. mysql数据库编码问题

    http://www.cnblogs.com/sunzn/archive/2013/03/14/2960248.html 修改/etc/my.cnf 添加: [mysql] default-chara ...

  3. ES TIPS

    1,Testing Analyzers Especially when you are new to Elasticsearch, it is sometimes difficult to under ...

  4. &lbrack;转&rsqb;linux系统磁盘分区之parted

    转自:http://blog.csdn.net/h249059945/article/details/12668793 对于linux的分区通常可以使用fdisk命令工具和parted工具对于分区表通 ...

  5. (转)Linux IO模式及 select、poll、epoll详解

    本文为转载,并作了部门调整.修改. [原文出处:https://segmentfault.com/a/1190000003063859] 同步IO和异步IO,阻塞IO和非阻塞IO分别是什么,到底有什么 ...

  6. HDU4527&plus;BFS

    模拟BFS搜索 对于一个将要爆炸的点,可能同时由多个点引起. /* 模拟搜索过程 */ #include<stdio.h> #include<stdlib.h> #includ ...

  7. Maven--构建企业级仓库(二)

    <Maven--搭建开发环境(一)> <Maven--构建企业级仓库(二)> <Maven—几个需要补充的问题(三)>              看到经历的两家公司 ...

  8. ZUFE 1035 字符宽度编码&lpar;字符串&rpar;

    Time Limit: 1 Sec  Memory Limit: 128 MB Description 你的任务是编写一个程序实现简单的字符宽度编码方法.规则如下:将任何2~9个相同字符的序列编码成2 ...

  9. 前言《iOS网络高级编程:iPhone和iPad的企业应用开发》(书籍学习)

    本书内容: 在客户端设备与服务器之间执行HTTP请求 管理客户端设备与服务器之间的数据负载 处理HTTP请求的错误 保护网络通信 改进网络通信的性能 执行Socket层的通信 实现推送通知 单个设备上 ...

  10. Python全栈之路----常用模块----xml处理模块

    xml是实现不同语言或程序之间进行数据交换的协议,跟json差不多,但json使用起来更简单,不过,古时候,在json还没诞生的黑暗年代,大家只能选择用xml呀,至今很多传统公司如金融行业的很多系统的 ...