当前位置: 首页 > news >正文

SA+ST表维护height+单调队列维护:CF1073G

https://www.luogu.com.cn/problem/CF1073G

lcp相关的,先跑个sa,然后height建个ST表

现在考虑询问,我们按A和B按 r k rk rk 排序。现在考虑B->A,反过来同理。

我们可以用单调队列维护,满足height是单增的。因为越往前lcp必然越短。同时要维护有多少个。然后对于当前后缀的答案就是单调队列的大小了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 400010
//#define M
//#define mo
struct node {int x, op; 
};
struct Node {int x, k; 
};
int n, m, i, j, k, T;
int tmp[N], bin[N], rk[N], sa[N], tot; 
int f[N/2][22], Log2[N]; 
int h[N], height[N], c[2], ans, na, nb, q; 
char s[N]; void psort() {memset(bin, 0, sizeof(bin)); int i; for(i=1; i<=n; ++i) bin[rk[i]]++; for(i=1; i<=max(n, 128ll); ++i) bin[i]+=bin[i-1]; for(i=n; i>=1; --i) sa[bin[rk[tmp[i]]]--]=tmp[i]; 
}int lcp(int i, int j) {if(i==j) return n-i+1; int l=rk[i]+1, r=rk[j]; int k=Log2[r-l+1]; return min(f[l][k], f[r-(1<<k)+1][k]); 
}void SA() {for(i=1; i<=n; ++i) rk[i]=s[i], tmp[i]=i; psort(); 
//	for(i=1; i<=n; ++i) printf("%lld ", sa[i]); printf("\n"); for(j=1; j<n; j<<=1) {for(i=n-j+1, k=0; i<=n; ++i) tmp[++k]=i; for(i=1; i<=n; ++i) if(sa[i]-j>0) tmp[++k]=sa[i]-j; psort(); tmp[sa[1]]=tot=1; for(i=2; i<=n; ++i) {if(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+j]!=rk[sa[i-1]+j]) ++tot; tmp[sa[i]]=tot; }memcpy(rk, tmp, sizeof(tmp)); }
//	for(i=1; i<=n; ++i) printf("%d ", sa[i]); printf("\n"); for(i=1; i<=n; ++i) {h[i]=max(h[i-1]-1, 0ll); j = sa[rk[i]-1]; while(s[i+h[i]] == s[j+h[i]]) ++h[i]; }
//	for(i=2; i<=n; ++i) printf("%d ", h[sa[i]]); 
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); q=read(); scanf("%s", s+1); SA(); for(i=2; i<=n; ++i) height[i]=f[i][0]=h[sa[i]]; for(k=1; k<=20; ++k) for(i=1, j=(1<<k-1)+1; i+(1<<k)-1<=n; ++i, ++j)f[i][k]=min(f[i][k-1], f[j][k-1]);for(i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1; while(q--) {na=read(); nb=read(); vector<node>v; for(i=1; i<=na; ++i) k=read(), v.pb({k, 0}); for(i=1; i<=nb; ++i) k=read(), v.pb({k, 1}); sort(v.begin(), v.end(), [] (node x, node y) { return rk[x.x]<rk[y.x]; }); stack<Node>z[2]; ans=c[0]=c[1]=0; 
//		z[v[0].op].push({n-v[0].x+1, 1}); 
//		c[v[0].op]+=n-v[0].x+1; for(i=1; i<na+nb; ++i) {auto  t=v[i-1]; int o = t.op, k=1, H=lcp(t.x, v[i].x); while(!z[o].empty() && z[o].top().x>=H) {auto t2 = z[o].top(); z[o].pop(); k+=t2.k, c[o]-=t2.x*t2.k; }z[o].push({H, k}); c[o]+=H*k; k=0; while(!z[o^1].empty() && z[o^1].top().x>=H) {auto t2 = z[o^1].top(); z[o^1].pop(); k+=t2.k, c[o^1]-=t2.x*t2.k; }if(k) z[o^1].push({H, k}), c[o^1]+=H*k; //			printf("(%d %d) %lld %lld\n", t.x, t.op, H, c[v[i].op^1]); ans+=c[v[i].op^1]; }printf("%lld\n", ans); }return 0;
}

相关文章:

SA+ST表维护height+单调队列维护:CF1073G

https://www.luogu.com.cn/problem/CF1073G lcp相关的&#xff0c;先跑个sa&#xff0c;然后height建个ST表 现在考虑询问&#xff0c;我们按A和B按 r k rk rk 排序。现在考虑B->A&#xff0c;反过来同理。 我们可以用单调队列维护&#xff0c;满足height是单增的。因为…...

Java中JVM、JRE和JDK三者有什么区别和联系?

任何语言或者软件的运行都需要环境。就像人要生活在空气中&#xff0c;鱼要活在水中&#xff0c;喜阴植物就不能放在阳光下暴晒一样&#xff0c;任何对象个体的存在都离不开其所需要的环境&#xff0c;编程语言亦是一样的。 java 语言的开发运行&#xff0c;也离不开 Java 语言…...

秋季期中考复现xj

flow analysis 1 What is the backdoor file name that comes with the server?( Including file suffix) 服务器自带的后门文件是什么&#xff1f;&#xff08;含文件后缀&#xff09; 题目还要求最后把那个文件名MD5一下&#xff0c;再去提交 开始的前三题是流量分析的&…...

【代码随想录】算法训练营 第十四天 第六章 二叉树 Part 1

递归遍历 递归法讲究的就是一个格式&#xff0c;在外边再定义一个用于递归求解的函数reverser&#xff0c;参数是递归的二叉树当前根节点和用于保存遍历得到的答案序列的vector容器&#xff1b; 函数中的格式就是&#xff0c;先写递归终止条件&#xff0c;也就是遍历的结点为…...

【访问控制】—>《熟练使用ACL进行上网行为管理》

✍ 标准和高级ACL功能介绍&#xff1b; ✍ 思科和华为ACL功能有什么区别&#xff1f; ✍ 现网中ACL都有哪些使用场景&#xff1f; -- ACL - 访问控制列表 - 控制&#xff1a; 能通/不能通 -- ACL - 结合功能 list - 简化版本的行为管理 -- 插件性质的功能 --…...

MySQL外键,表与表的关系,多表查询,Navicat软件

外键 MySQL可以使用外键来保持表之间的关系完整性。 要设置外键&#xff0c;可以按照以下步骤进行操作&#xff1a; 在创建表时&#xff0c;使用FOREIGN KEY关键字来指定外键列&#xff1a; CREATE TABLE table1 (id INT PRIMARY KEY,name VARCHAR(50),table2_id INT,FOREI…...

Linux系统镜像备忘

阿里镜像源&#xff1a; ubuntu ubuntu-releases安装包下载_开源镜像站-阿里云 centos centos-stream安装包下载_开源镜像站-阿里云...

Docker容器端口在主机的映射

Docker容器端口在主机的映射 Docker 允许你在启动容器时进行多个端口映射&#xff0c;以便将容器内部的端口映射到宿主机上的不同端口。你可以使用-p或--publish标志来指定端口映射。以下是一些示例&#xff0c;说明如何在 Docker 启动容器时进行多个端口映射&#xff1a; 映…...

Spring Boot中RedisTemplate的使用

当前Spring Boot的版本为2.7.6&#xff0c;在使用RedisTemplate之前我们需要在pom.xml中引入下述依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId><vers…...

GSCoolink GSV6183 带嵌入式MCU的MIPI D-PHY 转 DP/eDP

Gscoolink GSV6183是一款高性能、低功耗的MIPI D-PHY到DisplayPort/eDP 1.4转换器。通过集成基于RISC-V的增强型微控制器&#xff0c;GSV6183创造了一种具有成本效益的解决方案&#xff0c;提供了上市时间优势。MIPI D-PHY接收器支持CSI-2版本1.3和DSI版本1.3&#xff0c;每条通…...

Linux文件系统 struct dentry 结构体解析

文章目录 前言一、目录项简介二、struct dentry2.1 简介2.2 dentry和inode关联2.3 目录项视图2.4 目录项状态2.5 目录项特点 三、dentry cache3.1 简介3.2 dentry cache 初始化3.3 dentry cache 查看 四、dentry与mount、file的关联五、其他参考资料 前言 这两篇文章介绍了: V…...

C++——vector

目录 vector vector常用接口 构造函数 operator[]size() 迭代器 范围for capacity() resize() reverse() push_back和pop_back insert erase() algorithm::sort 注意 迭代器失效 vector vector单词直译是向量的意思&#xff0c;这个容器可以容纳不同的类型数据&am…...

html5语义化标签

目录 前言 什么是语义化标签 常见的语义化标签 语义化的好处 前言 HTML5 的设计目的是为了在移动设备上支持多媒体。之前网页如果想嵌入视频音频&#xff0c;需要用到 flash &#xff0c;但是苹果设备是不支持 flash 的&#xff0c;所以为了改变这一现状&#xff0c;html5 …...

SQL Server批量删除数据库中的表

如果想要删除数据库中temp 开头的中间表 1. SQL 语句实现 use [DBName] --todo go select drop table name from sys.tables where name like temp% go 将查询结果粘贴到数据库中运行 2. 数据库 单击目标数据库中的Tables ,然后按F7 键&#xff0c;按Name 进行排序&…...

使用SecScanC2构建P2P去中心化网络实现反溯源

个人博客: xzajyjs.cn 前言 这款工具是为了帮助安全研究人员在渗透测试过程中防止扫描被封禁、保护自己免溯源的一种新思路。其利用到了区块链中的p2p点对点去中心化技术构建以来构建代理池。 工具链接&#xff1a;https://github.com/xzajyjs/SecScanC2 实验过程 该工具分为…...

【API篇】七、Flink窗口

文章目录 1、窗口2、分类3、窗口API概览4、窗口分配器 在批处理统计中&#xff0c;可以等待一批数据都到齐后&#xff0c;统一处理。但是在无界流的实时处理统计中&#xff0c;是来一条就得处理一条&#xff0c;那么如何统计最近一段时间内的数据呢&#xff1f; ⇒ 窗口的概念&…...

软件测试面试1000问(含文档)

前前后后面试了有20多家的公司吧&#xff0c;最近抽空把当时的录音整理了下&#xff0c;然后给大家分享下 开头都是差不多&#xff0c;就让做一个自我介绍&#xff0c;这个不用再给大家普及了吧 同时&#xff0c;我也准备了一份软件测试视频教程&#xff08;含接口、自动化、…...

进阶课4——随机森林

1.定义 随机森林是一种集成学习方法&#xff0c;它利用多棵树对样本进行训练并预测。 随机森林指的是利用多棵树对样本进行训练并预测的一种分类器&#xff0c;每棵树都由随机选择的一部分特征进行训练和构建。通过多棵树的集成&#xff0c;可以增加模型的多样性和泛化能力。…...

【Docker】Dockerfile使用技巧

开启Buildkit BuildKit是Docker官方社区推出的下一代镜像构建神器&#xff0c;可以更加快速&#xff0c;有效&#xff0c;安全地构建docker镜像。 尽管目前BuildKit不是Docker的默认构建工具&#xff0c;但是完全可以考虑将其作为Docker&#xff08;v18.09&#xff09;的首选…...

一招解决“请在微信客户端中打开链接”

一招解决“请在微信客户端中打开链接”-遇见你与你分享 在浏览器访问网站&#xff0c;却提示“请在微信客户端打开链接”。虽然这个情况你可能从未遇到过&#xff0c;但对于爱折腾的小伙伴&#xff0c;确是一道拦路虎 其实解决办法很简单&#xff0c;就是新建一个UA&#xff1…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...