CF1098F Ж-function
【题意】
给你一个字符串 s s s,每次询问给你 l , r l, r l,r,让你输出 s s = s l , r ss=s_{l,r} ss=sl,r中 ∑ i = 1 r − l + 1 L C P ( s s i , s s 1 ) \sum_{i=1}^{r-l+1}LCP(ss_i,ss_1) ∑i=1r−l+1LCP(ssi,ss1)。
【思路】
和前一道题一样,用了根号做法。
可以把贡献拆成两部分,第一部分是求原串中的LCP之和,显然这样有一些超过 r r r,而这些都是border,然后就用[BJWC2018] Border 的四种求法的方法来修正这一部分的贡献即可。
第一部分先用SA,然后正着扫反着扫用分块维护。
第二部分就在前一题的基础上多进行一些对长度的分类讨论就行。
#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e5 + 10, B = 250;
const int mod = 1e9 + 7;int n, m; char s[N];
int sa[N], rk[N], height[N], st[N][20], lg[N];
vector<pair<int, int>> ask[N];
ll ans[N];
int val[N], hsh[N];
int period[N], nxt[N], jump[N], to[N], f[N];void SA() {vector<int> x(N), y(N), c(N);int m = 256;for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;for (int i = 1; i <= m; i++) c[i] += c[i - 1];for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;for (int k = 1; k <= n; k <<= 1) {int num = 0;for (int i = n - k + 1; i <= n; i++) y[++num] = i;for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i] - k;for (int i = 1; i <= m; i++) c[i] = 0;for (int i = 1; i <= n; i++) c[x[i]]++;for (int i = 2; i <= m; i++) c[i] += c[i - 1];for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;swap(x, y); x[sa[1]] = num = 1;for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;if (num == n) break;m = num;}for (int i = 1; i <= n; i++) rk[sa[i]] = i;int k = 0;for (int i = 1; i <= n; i++) {if (rk[i] == 1) continue;if (k) k--;int j = sa[rk[i] - 1];while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;height[rk[i]] = k;}lg[0] = -1;for (int i = 1; i <= n; i++) {st[i][0] = height[i];lg[i] = lg[i >> 1] + 1;}for (int j = 1; j <= 18; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}
}
int getlcp(int i, int j) {i = rk[i], j = rk[j];if (i > j) swap(i, j);i++;int t = lg[j - i + 1];return min(st[i][t], st[j - (1 << t) + 1][t]);
}namespace block {int cnt, L[N / B + 10], R[N / B + 10], belong[N];int siz[N / B + 10], num[N / B + 10][B + 10], val[N / B + 10][B + 10];ll sum[N / B + 10];bool vis[N];void init() {cnt = 0;memset(siz, 0, sizeof(siz));memset(num, 0, sizeof(num));memset(val, 0, sizeof(val));memset(sum, 0, sizeof(sum));memset(vis, 0, sizeof(vis));for (int l = 1, r; l <= n; l = r + 1) {r = min(n, l + B - 1);cnt++;L[cnt] = l, R[cnt] = r;for (int i = l; i <= r; i++) {belong[i] = cnt;}}}void limit(int x) {for (int i = 1; i <= cnt; i++) {int tot = 0;while (siz[i] && val[i][siz[i]] >= x) {tot += num[i][siz[i]];sum[i] -= 1ll * num[i][siz[i]] * val[i][siz[i]];siz[i]--;}if (tot) {siz[i]++;num[i][siz[i]] = tot;val[i][siz[i]] = x;sum[i] += 1ll * tot * x;}}}ll calc(int l, int r) { // l < rl++;ll ret = 0;if (belong[l] == belong[r]) {for (int i = l; i <= r; i++) if (vis[i]) {ret += getlcp(l - 1, i);}}else {int t;t = belong[r];for (int i = L[t]; i <= r; i++) if (vis[i]) {ret += getlcp(l - 1, i);}r = L[t] - 1;t = belong[l];for (int i = l; i <= R[t]; i++) if (vis[i]) {ret += getlcp(l - 1, i);}l = R[t] + 1;while (l <= r) {ret += sum[belong[l]];l += B;}}return ret;}void ins(int pos) {vis[pos] = 1;int len = n - pos + 1;int t = belong[pos];sum[t] += len;for (int i = 1; i <= siz[t]; i++) {if (val[t][i] == len) {num[t][i]++;return;}}siz[t]++;num[t][siz[t]] = 1;val[t][siz[t]] = len;for (int i = siz[t]; i > 1; i--) {if (val[t][i] < val[t][i - 1]) {swap(val[t][i], val[t][i - 1]);swap(num[t][i], num[t][i - 1]);}else {break;}}}
}int gethsh(int l, int r) {return (hsh[r] - 1ll * hsh[l - 1] * val[r - l + 1] % mod + mod) % mod;
}ll getsum(int a1, int d, int n) {return 1ll * a1 * n - 1ll * d * n * (n - 1) / 2;
}int main() {// freopen("in.in", "r", stdin);// freopen("out.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(nullptr);clock_t start = clock();cin >> (s + 1) >> m;n = strlen(s + 1);SA();// for (int i = 1; i <= n; i++) {// cout << sa[i] << " \n"[i == n];// }// for (int i = 1; i <= n; i++) {// cout << height[i] << " \n"[i == n];// }for (int i = 1; i <= m; i++) {int l, r; cin >> l >> r;ans[i] = r - l + 1;if (l < r) ask[l].push_back({r, i});}block::init();for (int ki = 1; ki <= n; ki++) {block::limit(height[ki]); int l = sa[ki]; for (auto [r, id] : ask[l]) {ans[id] += block::calc(l, r);}block::ins(l);}block::init();height[n + 1] = 0;for (int ki = n; ki >= 1; ki--) {block::limit(height[ki + 1]); int l = sa[ki]; for (auto [r, id] : ask[l]) {ans[id] += block::calc(l, r);}block::ins(l);}val[0] = 1;for (int i = 1; i <= n; i++) {val[i] = 1ll * val[i - 1] * 257 % mod;hsh[i] = (1ll * hsh[i - 1] * 257 + s[i] - 'a') % mod;}map<int, int> last;for (int i = 1; i <= n; i++) nxt[i] = n + 1;for (int ki = 1; ki <= n - B + 1; ki++) {f[ki] = ki - 1;for (int i = ki + 1, j = ki - 1; i <= ki + B - 1; i++) {while (j > ki - 1 && s[j + 1] != s[i]) j = f[j];if (s[j + 1] == s[i]) j++;f[i] = j;}period[ki] = ki + B - 1 - f[ki + B - 1];int now = gethsh(ki, ki + B - 1);if (last[now]) nxt[last[now]] = ki;last[now] = ki;}last.clear();for (int i = 1; i <= n; i++) jump[i] = i;for (int i = n - B + 2; i <= n + 1; i++) to[i] = n;for (int i = n - B + 1; i >= 1; i--) {int j = i + period[i];if (j <= n && nxt[i] == j) to[i] = to[j], jump[i] = jump[j];else {for (int j = i + B - 1, k = i + (B - 1) % period[i]; j <= n; j++) {if (s[j] != s[k]) break;to[i] = j;k++; if (k == i + period[i]) k = i;}}}// clock_t end = clock();// cout << (double)(end - start) / CLOCKS_PER_SEC << endl;for (int l = 1; l < n; l++) {for (auto [r, id] : ask[l]) {ll ret = 0;if (r - l + 1 <= 2 * B) {for (int i = l + 1; i <= r; i++) {int t = r - i + 1;if (gethsh(l, l + t - 1) == gethsh(i, r)) {ret -= getlcp(l, i);ret += t;}}}else {for (int t = 1; t < B; t++) {if (gethsh(l, l + t - 1) == gethsh(r - t + 1, r)) {ret -= getlcp(l, r - t + 1);ret += t;}}int x = nxt[l];int len = period[l];int count = 0;while (to[x] < r) {// assert((++count) <= 500);if (to[x] - x >= to[l] - l && (to[x] - x) % len == (to[l] - l) % len) {x = to[x] - (to[l] - l);int t = r - x + 1;if (gethsh(l, l + t - 1) == gethsh(x, r)) {ret -= getlcp(l, x);ret += t;}}x = nxt[jump[x]];}if (x + B - 1 <= r) {int len1 = to[l] - l + 1;int len2 = to[x] - x + 1;//>int t;if (x + len1 - 1 < r) {t = (r - x - len1) / len + 1;x += t * len;len2 -= t * len;}if (x + B - 1 <= r && len2 > len1) { //x + len1 - 1 >= rt = min(len2 - len1 - 1, r - B + 1 - x) / len + 1;ret -= 1ll * (to[l] - l + 1) * t;ret += getsum(r - x + 1, len, t);len2 -= len * t;x += len * t;}//==if (x + B - 1 <= r && len1 == len2) {ret -= getlcp(l, x);ret += r - x + 1;len2 -= len;x += len;}//<if (x + B - 1 <= r) {t = (r - B + 1 - x) / len + 1;ret += 1ll * (r - to[x]) * t;}}}ans[id] += ret;}}// clock_t end2 = clock();// cout << (double)(end2 - end) / CLOCKS_PER_SEC << endl;// cout << (double)(end2 - start) / CLOCKS_PER_SEC << endl;for (int i = 1; i <= m; i++) {cout << ans[i] << "\n";}// clock_t end3 = clock();// cout << (double)(end3 - start) / CLOCKS_PER_SEC << endl;
}
相关文章:
CF1098F Ж-function
【题意】 给你一个字符串 s s s,每次询问给你 l , r l, r l,r,让你输出 s s s l , r sss_{l,r} sssl,r中 ∑ i 1 r − l 1 L C P ( s s i , s s 1 ) \sum_{i1}^{r-l1}LCP(ss_i,ss_1) ∑i1r−l1LCP(ssi,ss1)。 【思路】 和前一道题一样&#…...
Python 函数魔法书:基础、范例、避坑、测验与项目实战
Python 函数魔法书:基础、范例、避坑、测验与项目实战 内容简介 本系列文章是为 Python3 学习者精心设计的一套全面、实用的学习指南,旨在帮助读者从基础入门到项目实战,全面提升编程能力。文章结构由 5 个版块组成,内容层层递进…...
vim交换文件的作用
1.数据恢复:因为vim异常的退出,使用交换文件可以恢复之前的修改内容。 2.防止多人同时编辑:vim检测到交换文件的存在,会给出提示,以避免一个文件同时被多人编辑。 (vim交换文件的工作原理:vim交换文件的工作…...
[NOI1995] 石子合并
[NOI1995] 石子合并 题目描述 在一个圆形操场的四周摆放 N N N 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 2 2 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 试设计出一个算法,计算出将 …...
真正的智能与那只蝴蝶
“蝴蝶效应”可以展开为对智能本质与大算力关系的追问,其中“蝴蝶”作为隐喻可能指向多重维度——从混沌理论的“蝴蝶效应”到庄子“物我两忘”的蝴蝶之梦。这种并置本身暗示了智能与宇宙秩序、认知边界之间的深刻张力。以下从三个层面展开分析:一、混沌…...
C++小病毒-1.0勒索(更新次数:2)
内容供学习使用,不得转卖,代码复制后请1小时内删除,此代码会危害计算机安全,谨慎操作 在C20环境下,并在虚拟机里运行此代码!,病毒带来后果自负! 使用时请删除在main()里的注释,并修改位置至C:\\(看我代码注释)//可以改成WIN Main() #include <iostream> #i…...
Node.js 的底层原理
Node.js 的底层原理 1. 事件驱动和非阻塞 I/O Node.js 基于 Chrome V8 引擎,使用 JavaScript 作为开发语言。它采用事件驱动和非阻塞 I/O 模型,使其轻量且高效。通过 libuv 库实现跨平台的异步 I/O,包括文件操作、网络请求等。 2. 单线程事…...
基于Django的豆瓣影视剧推荐系统的设计与实现
【Django】基于Django的豆瓣影视剧推荐系统的设计与实现(完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统采用了Python作为后端开发语言,采用Django作为后端架构,结…...
P10638 BZOJ4355 Play with sequence Solution
Description 给定 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1,a2,⋯,an),有 m m m 个操作,分以下三种: assign ( l , r , k ) \operatorname{assign}(l,r,k) assign(l,r,k):对每个 i ∈ [ l , r ] i \…...
MySQL误删数据怎么办?
文章目录 1. 从备份恢复数据2. 通过二进制日志恢复数据3. 使用数据恢复工具4. 利用事务回滚恢复数据5. 预防误删数据的策略总结 在使用MySQL进行数据管理时,误删数据是一个常见且具有高风险的操作。无论是因为操作失误、系统故障,还是不小心执行了删除命…...
项目测试之MockMvc
文章目录 基础基础概念Mockxxx一般实现文件位置 实战MockMvc与Test注解不兼容RequestParams参数RequestBody参数 基础 基础概念 定义:是Spring框架提供的一种用于测试Spring MVC控制器的工具,它允许开发者在不启动完整的web服务器的情况下,…...
Unbutu虚拟机+eclipse+CDT编译调试环境搭建
问题1: 安装CDT,直接Help->eclipse Market space-> 搜cdt , install,等待重启即可. 问题2:C变量不识别vector ’could not be resolved 这是库的头文件没加好,右键Properties->C Build->Enviroment,增加…...
时间轮:XXL-JOB 高效、精准定时任务调度实现思路分析
大家好,我是此林。 定时任务是我们项目中经常会遇到的一个场景。那么如果让我们手动来实现一个定时任务框架,我们会怎么做呢? 1. 基础实现:简单的线程池时间轮询 最直接的方式是创建一个定时任务线程池,用户每提交一…...
CTF-web: Python YAML反序列化利用
PyYAML存在以下几个特殊标签,如果这些标签被不安全的解析,会造成解析漏洞 从 PyYaml 版本 6.0 开始,load 的默认加载器已切换到 SafeLoader,以降低远程代码执行的风险。更新后易受攻击的是 yaml.unsafe_load 和 yaml.load(input, Loaderyaml.UnsafeLoade…...
代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分
类似于回溯算法中的拆分回文串题目是要求拆分字符串,问这些字符串是否出现在字典里。但这道题可以反着来考虑,从字典中的单词能不能组成所给定的字符串 如果这样考虑, 这个字符串就背包,容器字典中的单词就是一个一个物品问题就转…...
ML基础-Jupyter notebook中的魔法命令
在 Jupyter Notebook 或 IPython 环境中,“魔法命令”(Magic Commands)是一些以百分号(%)或惊叹号(!)开头的特殊命令,用于执行一些与代码运行环境相关的操作,而不仅仅是执行普通的 P…...
Zookeeper入门部署(单点与集群)
本篇文章基于docker方式部署zookeeper集群,请先安装docker 目录 1. docker初期准备 2.启动zookeeper 2.1 单点部署 2.2 集群部署 3. Linux脚本实现快速切换启动关闭 1. docker初期准备 拉取zookeeper镜像 docker pull zookeeper:3.5.6 如果拉取时间过长…...
Kafa分区策略实现
引言 Kafka 的分区策略决定了生产者发送的消息会被分配到哪个分区中,合理的分区策略有助于实现负载均衡、提高消息处理效率以及满足特定的业务需求。 轮询策略(默认) 轮询策略是 Kafka 默认的分区策略(当消息没有指定键时&…...
Pyside/Pyqt中QWebEngineView和QWebEnginePage的区别
在 PySide/Qt 的 WebEngine 模块中,QWebEngineView 和 QWebEnginePage 是两个紧密相关但职责不同的类。以下是它们的核心区别和关系: 1. 职责区分 类名核心职责模块归属QWebEngineView作为可视化的窗口部件(Widget),负…...
Kafka的内部通信协议
引言 kafka内部用到的常见协议和优缺点可以看看原文 Kafka用到的协议 本文奖详细探究kafka核心通信协议和高性能的关键 网络层通信的实现 基于 Java NIO:Kafka 的网络通信层主要基于 Java NIO 来实现,这使得它能够高效地处理大量的连接和数据传输。…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
