首页 > 其他分享 >CF1175F The Number of Subpermutations 对自己的警告--zhengjun

CF1175F The Number of Subpermutations 对自己的警告--zhengjun

时间:2023-07-14 12:22:24浏览次数:52  
标签:__ lg Subpermutations -- Number long int using

太久没见过启发式合并了,然后没想出做法。

首先笛卡尔树建出来。

然后直接枚举跨过 \(mid\) 的长度为 \(a_{mid}\) 的区间,RMQ \(O(1)\) 验证即可。

发现这样的区间个数不超过左右区间大小的较小值,时间复杂度:\(O(n\log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+10,K=__lg(N)+2;
int n,a[N],buf[N],f[K][N];
int top,stk[N],ls[N],rs[N],L[N],R[N];
bool chk(int l,int r){
	int k=__lg(r-l+1);
	return max(f[k][l],f[k][r-(1<<k)+1])<l;
}
int ans;
void dfs(int u){
	if(ls[u])dfs(ls[u]),L[u]=L[ls[u]];
	else L[u]=u;
	if(rs[u])dfs(rs[u]),R[u]=R[rs[u]];
	else R[u]=u;
	int st=L[u],ed=u;
	st=max(st,u-a[u]+1),ed=min(ed,R[u]-a[u]+1);
	for(int i=st;i<=ed;i++)ans+=chk(i,i+a[u]-1);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)f[0][i]=buf[a[i]],buf[a[i]]=i;
	for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)
		f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
	for(int i=1;i<=n;i++){
		for(;top&&a[stk[top]]<a[i];top--)ls[i]=stk[top];
		rs[stk[top]]=i,stk[++top]=i;
	}
	dfs(rs[0]);
	cout<<ans;
	return 0;
}

标签:__,lg,Subpermutations,--,Number,long,int,using
From: https://www.cnblogs.com/A-zjzj/p/17553377.html

相关文章

  • 2023.7.14
    学习java中的类面向对象与面向过程面向过程:强调的是功能行为,以函数为最小单位,考虑怎么做。面向对象:强调具备了功能的对象,以类/对象为最小单位类与对象的关系类:对一类事物的描述,是抽象的、概念上的定义对象:是实际存在的该类事物的每个个体,因而也称为实例(instance)面向对象......
  • flutter provider create: (_) => xxxx(),
    Provider通常使用ChangeNotifierProvider配合ChangeNotifier一起来实现状态的管理与Widget的更新。ChangeNotifierProvider本质上其实就是Widget,它作为父节点Widget,可将数据共享给其所有子节点Widget使用或更新;创建model,继承ChangeNotifier,用来实现数据更新的通知并监听......
  • 使用Python进行文件复制
    一、序公司有部分内网电脑文件转到有网电脑二、解决思路通过共享地址将文件转到其他电脑上三、解决步骤1、先在我的电脑,输入电脑地址,输入账户密码点击记住凭证2.实现代码如下展开代码importshutilimportos#将需要的文件拷到需要的路径......
  • linux文件内容查看命令
    1、https://www.cnblogs.com/my-first-blog-lgz/p/13353051.html文件内容查看 1.cat:从第一行开始显示文件内容。用来读文章,或者读取配置文件 2.tac:从最后一行开始显示,可以看出tac是cat倒着写。 3.nl:显示的时候,顺便输出行号。看代码的时候希望显示行号。 4.more:一页一页显示......
  • httplib 库介绍与使用
    说明:cpp-httplib是个开源的库,是一个c++封装的http库,使用这个库可以在linux、windows平台下完成http客户端、http服务端的搭建,这是一个多线程“阻塞”HTTP库。使用起来非常方便,只需要包含头文件httplib.h即可。源码库地址:https://github.com/yhirose/cpp-httplib httplib......
  • 磁盘
    挂载磁盘mount${文件系统}${挂载点路径}将指定文件系统挂载到某一路径下:mount/dev/mapper/file-file/file卸载磁盘umount${挂载点路径}卸载指定路径下挂载的文件系统:umount/filedf检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了多少空间,目前还......
  • 在vm-17版本上安装centos 8.5 版本的Linux操作系统
    1、新建虚拟机 2、选择安装模式 3、选择虚拟机硬件兼容性,选择默认的 4、客户端操作系统安装选择 5、选择安装的操作系统类型 6、虚拟机命名和存放路径修改 7、处理器内核配置 8、系统内存放分配,选择默认的 9、选择网络连接模式 10、选择控制器 11......
  • C#基础
    重生之再学C# 1、第一章类-----Class参考:https://www.runoob.com/csharp/csharp-class.html定义一个类时,也就定义类的对象由什么组成  和在这个对象上可执行什么操作。对象就是类的实例,构成   类的方法和变量   称为类的成员。 访问标识符<access......
  • Spring的生命周期详解
    Spring的生命周期Spring框架是一个非常流行的Java企业级开发框架,它提供了很多强大的功能,包括依赖注入、AOP、事务管理等。在使用Spring框架时,了解Spring的生命周期非常重要,可以帮助我们更好地理解Spring框架的工作原理。Spring的生命周期可以分为三个阶段:实例化阶段、初始化阶段......
  • 成语积累 20230714
    鸢飞戾天:鸢:又名黑耳鸢,一种凶猛的鸟;戾:至,到。比喻为功名利禄而极力高攀,用于形容势利小人。作谓语,定语。出处:鸢飞戾天,鱼跃于渊。(万物各得其所)例句:~者,望峰息心。经纶世务者,窥谷忘返。即鹿无虞:进山打鹿,没有熟悉地形和鹿性的虞官帮助,那是白费力气。形容做事条件不成熟就草率行事,必定劳......