首页 > 其他分享 >线段树维护哈希

线段树维护哈希

时间:2022-10-16 22:22:30浏览次数:72  
标签:sz 线段 枚举 哈希 序列 维护

显然两个区间的哈希值是可以合并的,所以线段树可以维护区间的哈希值。

设左儿子的长度和哈希值分别为 \(sz_a,h_a\),右儿子的长度和哈希值分别为 \(sz_b,h_b\),合并后的长度为 \(sz_a + sz_b\),哈希值为 \(h_a \times base^{sz_b} + h_b\)。

1. CF213E Two Permutations

枚举 \(b\) 的值区间 \([x,x+n-1]\),令 \(pos_{b_x} = x\),那么我们需要判断 \([b_{pos_{x-n+1}},b_{pos_x}]\) 在原排列里构成的子序列的哈希值是否与排列 \(a\) 整体加 \(x-1\) 的哈希值相等。类似滑动窗口,每次添加、删除一个数,然后维护整个序列的哈希值即可。

2. CF452F Permutation & P2757 [国家集训队]等差子序列

判断序列里是否存在一个子序列是三元等差数列,可以枚举中间项 \(b\),如果存在公差 \(k\) 使得 \(b-k,b+k\) 在序列中出现在 \(b\) 的异侧就是 YES,否则就是 NO。但是直接枚举 \(b,k\) 是 \(O(n^2)\) 的。

可以考虑优化掉枚举公差 \(k\) 的过程。从小到大枚举 \(b\),维护一个 01 串表示 \(x\) 是否出现过,那么如果串不是回文的就表示存在一个 \(k\) 满足 \(x-k\) 出现过而 \(x+k\) 没出现过,符合判定条件。于是直接线段树维护即可。

标签:sz,线段,枚举,哈希,序列,维护
From: https://www.cnblogs.com/zltzlt-blog/p/16797435.html

相关文章

  • Redis数据结构之哈希
    目录Redis数据结构之哈希写入获取数据修改数据删除数据删除所有数据查看key中指定的field是否存在若value中没有相应的field,则创建获取多个值获取所有的key和value获取所......
  • Ansible 创建用户配置密码通过哈希加密的方式
    创建用户配置密码通过哈希加密的方式  [libin@libinansible]$vimrhca447-26.yaml----name:createuserandset  hosts:web  tasks:  -name:c......
  • CF240F (26颗线段树计数)
    题目链接:Topcoder----洛谷题目大意:给定一个长为n的由a到z组成的字符串,有m次操作,每次操作将[l,r]这些位置的字符进行重排,得到字典序最小的回文字符串,如果无法操作就......
  • 布隆过滤器是否好用,得看哈希函数写成啥样
    作者:小傅哥沉淀、分享、成长,让自己和他人都能有所收获!......
  • 查找算法与哈希表
    三分查找应用场景:求下列一元二次函数的极大值\[ax^2+bx+c\]#include<stdio.h>intternary_search(int*arr,intl,intr){inttri,m1,m2;do{......
  • 【数学篇】05 # 如何用向量和坐标系描述点和线段?
    说明【跟月影学可视化】学习笔记。坐标系与坐标映射​​HTML​​:采用的是窗口坐标系,以参考对象(参考对象通常是最接近图形元素的position非static的元素)的元素盒子左上角......
  • 线段树模板
    线段树是一种通用的数据结构,能够处理满足结合律的信息。前置知识线段树基础版structnode{intl,r;//TODO:informationandtagintlazy,val;......
  • 对象数组:用于维护类的多个对象
    对象数组创建数组,来维护多个对象。将对象存到数组的语法:类名[]数组名=new类名[];例如:Studentstu1=newStudent();Studentstu2=newStudent();Studentstu3=new......
  • DEMO:表维护视图相关维护及调用
    新建一个数据库表设置成可维护这里可以se11创建表维护视图也可以直接在刚才的界面点新建即可。另外,表字段里有时间和日期。想在创建和修改行项目的时候,日期和时间字段自动填......
  • Greenplum数据库数据分片策略Hash分布——计算哈希值和映射
    哈希Hash分布是Greenlum最常用的数据分布方式。根据预定义的分布键(distributedbykey)计算用户数据的哈希值,然后把哈希值映射到某个segment上。分布键可以包含多个字段。......