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

哈希问题的一类技巧

浅谈处理哈希问题的一类方法-线段树维护哈希

前言

一个初三蒟蒻粗浅的认知和总结,dalao不喜勿喷。分享的题也大都很水,仅是代表浅层理解。

简介/概括

哈希是一种常用的算法。我们在oi中使用哈希的主要目的是将难以直接处理、维护、比较的对象映射到范围小/便于维护/便于处理/便于比较的对象上。

映射的方式是哈希函数 $hash(x)$,设计哈希函数时会考虑对象的特性,并尽可能避免冲突。

通常,我们时常会把研究对象映射到整数上,这样就会出现溢出的问题,解决方法无非就两种:

1.自然溢出

就是不管它,让它自行溢出,根据溢出值来比较。仅限于long long类型

2.双哈希

同时设计两种不同哈希函数进行维护。可大幅提升准确率,减少冲突概率。

字符串哈希

哈希里面比较常见的一种,就是把一个字符串看成一个 $n$ 进制数,把字符串弄成一个类似键值的东西。

对字符串作哈希后,可以进行高效的比较、取子串等操作,有时还会用线段树去维护它(一般带修)。

总而言之,字符串哈希是处理字符串问题的一种常见思路。

CF580E Kefa and Watch

题意描述

维护一种由数字构成字符数组,可以执行以下操作:

1.格式:l r c,将l~r都赋值为$c$

2.格式: l r d,询问l~r是否有长度为$d$的循环节

solve

使用线段树去维护这个字符串哈希值。

关于怎样判断一个字符串 $s$ 有长度为 $d$ 的循环节,可以证明字符串 $s$ 有长度为 $d$ 的循环节等价于 $s[1...n-d]=s[d+1...n]$ ($s[l,r]$ 表示 $s$ 从 $l$ 到$r$ 的子串)。

使用线段树维护子串的哈希值,就可以完成以上比较了。

code


#include<iostream>
#include<cstdio>
#include<string>
#define int long long
#define N 1000007
using namespace std;
struct Sigement{string s;int mod,pw[100007],seed,note[100007];struct Tr{int tag,value;}tree[500007];void init(){int len=s.size();pw[0]=1;note[0]=1;for(int i=1;i<len+4;i++){pw[i]=pw[i-1]*seed%mod;note[i]=note[i-1]+pw[i];note[i]%=mod;}}void pushup(int l,int r,int pos){int mid=(l+r)/2;tree[pos].value=tree[pos*2].value*pw[r-mid]%mod+tree[pos*2+1].value;tree[pos].value%=mod;}void pushdown(int k,int l,int r,int pos){int mid=(l+r)/2;tree[pos*2].tag=k;tree[pos*2].value=(k+'0')*note[mid-l]%mod;tree[pos*2+1].tag=k;tree[pos*2+1].value=(k+'0')*note[r-mid-1]%mod;tree[pos].tag=-1;}void build(int l,int r,int cnt){tree[cnt].tag=-1;if(l==r){tree[cnt].value=s[l];return ;}int mid=(l+r)/2;build(l,mid,cnt*2);build(mid+1,r,cnt*2+1);pushup(l,r,cnt);}void update(int l,int r,int L,int R,int k,int cnt){if(L<=l&&r<=R){tree[cnt].tag=k;tree[cnt].value=(k+'0')*note[r-l]%mod;return ;}int mid=(l+r)/2;if(tree[cnt].tag!=-1){pushdown(tree[cnt].tag,l,r,cnt);}if(L<=mid){update(l,mid,L,R,k,cnt*2);}if(R>mid){update(mid+1,r,L,R,k,cnt*2+1);}pushup(l,r,cnt);}int query(int l,int r,int L,int R,int cnt){if(L<=l&&r<=R){return tree[cnt].value;}int mid=(l+r)/2,ans=0;if(tree[cnt].tag!=-1){pushdown(tree[cnt].tag,l,r,cnt);}if(L<=mid){ans+=query(l,mid,L,R,cnt*2);}if(R>mid){ans=ans*pw[min(r,R)-mid]%mod+query(mid+1,r,L,R,cnt*2+1);ans%=mod;}return ans;}
}tr1,tr2;
signed main(){int n,m,k;cin>>n>>m>>k;cin>>tr1.s;tr1.seed=128;tr1.mod=998244353;tr1.init();tr1.build(0,n-1,1);tr2.s=tr1.s;tr2.seed=131;tr2.mod=1e9+7;tr2.init();tr2.build(0,n-1,1);for(int i=1;i<=m+k;i++){int op;cin>>op;if(op==1){int l,r,c;cin>>l>>r>>c;tr1.update(0,n-1,l-1,r-1,c,1);tr2.update(0,n-1,l-1,r-1,c,1);}else{int l,r,d;cin>>l>>r>>d;l--;r--;if(r-l+1==d){cout<<"YES\n";}else if(tr1.query(0,n-1,l+d,r,1)==tr1.query(0,n-1,l,r-d,1)&&tr2.query(0,n-1,l+d,r,1)==tr2.query(0,n-1,l,r-d,1)){cout<<"YES\n";}else cout<<"NO\n";}}return 0;
}

P2757 [国家集训队] 等差子序列

题意描述

给一个数组,问它里面存不存在等差数列。

solve

这题比较抽象,它卡常。

首先,显然存在等差子序列等价于存在长度为 3 的等差子序列。

这大大降低了问题的难度。因为很容易可以想到枚举中间项,看看存不存在一个 $k$,使得在当前数两边分别存在等于 $a_i+k$ 与 $a_i-k$ 的数。

时间复杂度 $O(n^2)$。

接下来就是要优化上述过程。正难则反,我们可以考虑什么情况下无解。显然假如对于一个 $a_i$,$a_i-k$ 与 $a_i+k$ 都在它的左边,这就是无解的。

其实我们可以整一个桶,把便利过的 $a_i$ 都标记一下,再沿当前位置对折,看看重合的两个数是否都相等,若是,对于这个中项无解,否则有解。

这么说可能比较抽象,其实就是看以 $a_i$ 为中心,长度为 $2k-1$ 的 01 串是否是回文串。( $k$ 指最大的合法的 $k$ )

我们可以用权值线段树去维护这个字符串哈希,同时维护正序倒序哈希,就可以判回文了。

code

#include<bits/stdc++.h>
using namespace std;
int t,n,a[500005];
int mod=998244353,PW=2;
int hash1[2000005],hash2[2000005],pw[500005];
void pushup(int now,int l,int r){int mid=(l+r)/2;hash1[now]=(hash1[now*2]*1LL*pw[r-mid]%mod+hash1[now*2+1])%mod;hash2[now]=(hash2[now*2]+hash2[now*2+1]*1LL*pw[mid-l+1]%mod)%mod;
}
void add(int now,int l,int r,int x){if(l==r){hash1[now]=hash2[now]=1;}else{int mid=(l+r)/2;if(x<=mid) add(now*2,l,mid,x);if(x>mid) add(now*2+1,mid+1,r,x);pushup(now,l,r);}
}
int query1(int now,int l,int r,int L,int R){ if(L<=l&&r<=R){return hash1[now];}else{int mid=(l+r)/2;int ans=0;if(R<=mid) return query1(now*2,l,mid,L,R);if(L>mid) return query1(now*2+1,mid+1,r,L,R);ans+=query1(now*2,l,mid,L,R);ans=(ans*1LL*pw[min(r,R)-mid]%mod+query1(now*2+1,mid+1,r,L,R))%mod;return ans;}
}
int query2(int now,int l,int r,int L,int R){if(L<=l&&r<=R){return hash2[now];}else{int mid=(l+r)/2;int ans=0;if(R<=mid) return query2(now*2,l,mid,L,R);if(L>mid) return query2(now*2+1,mid+1,r,L,R);ans+=query2(now*2+1,mid+1,r,L,R);ans=(ans*1LL*pw[mid-max(l,L)+1]%mod+query2(now*2,l,mid,L,R))%mod;return ans;}
}
void build(int x,int l,int r){if(l==r){hash1[x]=0;hash2[x]=0;return ;}int mid=(l+r)/2;build(x*2,l,mid);build(x*2+1,mid+1,r);pushup(x,l,r);
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;pw[0]=1;for(int i=1;i<=500002;i++){pw[i]=pw[i-1]*1LL*PW%mod;}while(t--){cin>>n;build(1,1,n);for(int i=1;i<=n;i++){cin>>a[i];}int flg=0;for(int i=1;i<=n;i++){add(1,1,n,a[i]);int len=min(n-a[i]+1,a[i]);if(query1(1,1,n,a[i]-len+1,a[i])!=query2(1,1,n,a[i],a[i]+len-1)){flg=1;break;}}if(flg){cout<<"Y\n";}else cout<<"N\n";}return 0;
} 

其它类型的哈希

有时还会去用哈希维护一个难以直接维护、操作、比较的数列或集合等。这时就需要根据这个维护对象的特质构建哈希函数,有时还会套上数据结构。真是挺恶心的。

蒟蒻目前常见到的两种套路(dalao勿喷):

1.考虑顺序的数列

比如有个有序数列 $a$ , $|a|=n$,比较两个数列,我们可以使用以下哈希函数:

$$hash(a)=\sum_{i=1}{n}baseia_i$$

2.无序性集合

有个集合 $A$,判断两个集合是否相同时可以使用以下哈希函数:

$$hash(A)=\sum_{x \in A}base^x$$

P6688 可重集

这道题和上道题差不多难,就是不卡常好许多。

就是把每个数当做幂数,这样区间的 hash 值就和数字顺序无关了。

如对于数列 $x$,哈希方式为

$$ hash(x)=\sum_{i=1}nbase\mod p$$

日常线段树维护一下。

维护两个量,一个是哈希值,因为要区间加上 $k$,再维护最小值。

code

#include<iostream>
#include<cstdio>
using namespace std;
int n,q,a[1000007];
const int mod=1e9+7,base=2;
int pw[1000007],sum[4000007],minn[4000007];
void pushup(int now){minn[now]=min(minn[now*2],minn[now*2+1]);sum[now]=(sum[now*2]+sum[now*2+1])%mod;
}
void build(int now,int l,int r){if(l==r){sum[now]=pw[a[l]];minn[now]=a[l];return ;}int mid=(l+r)/2;build(now*2,l,mid);build(now*2+1,mid+1,r);pushup(now);
}
void upd(int now,int l,int r,int x,int y){if(l==r){sum[now]=pw[y];minn[now]=y;return ;}int mid=(l+r)/2;if(x<=mid) upd(now*2,l,mid,x,y);else upd(now*2+1,mid+1,r,x,y);pushup(now);
}
long long Qs(int now,int l,int r,int L,int R){if(L<=l&&r<=R){return sum[now];}int mid=(l+r)/2;long long ans=0;if(L<=mid) ans=(ans+Qs(now*2,l,mid,L,R))%mod;if(R>mid) ans=(ans+Qs(now*2+1,mid+1,r,L,R))%mod;return ans;
}
int Qm(int now,int l,int r,int L,int R){if(L<=l&&r<=R){return minn[now];}int mid=(l+r)/2;int ans=0x3f3f3f3f;if(L<=mid) ans=min(ans,Qm(now*2,l,mid,L,R));if(R>mid) ans=min(ans,Qm(now*2+1,mid+1,r,L,R));return ans;
}
void pri(int now,int l,int r){if(l==r){cout<<minn[now]<<" ";return ;}int mid=(l+r)/2;pri(now*2,l,mid);pri(now*2+1,mid+1,r);
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);pw[0]=1;for(int i=1;i<=1000000;i++){pw[i]=pw[i-1]*1LL*base%mod;}cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}build(1,1,n);while(q--){int op;cin>>op;if(op==0){int x,y;cin>>x>>y;upd(1,1,n,x,y);}else{int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;long long ans1,ans2,fi1,fi2;ans1=Qs(1,1,n,l1,r1);ans2=Qs(1,1,n,l2,r2);fi1=Qm(1,1,n,l1,r1);fi2=Qm(1,1,n,l2,r2);if(fi1>fi2){swap(ans1,ans2);swap(fi1,fi2);}if(ans1*1LL*pw[fi2-fi1]%mod==ans2){cout<<"YES\n";}else cout<<"NO\n";}}return 0;
}

Thanks For Your Reading!

by 积雨云 (xjhoi)

http://www.hskmm.com/?act=detail&tid=22469

相关文章:

  • CVPR-2025 | 具身导航指令高效生成!MAPInstructor:基于场景图的导航指令生成Prompt调整策略 - 详解
  • 2025 年无锡西门子产品供应商 TOP 企业品牌排行榜,PLC,高低压变频器,高低压电机代理分销商推荐
  • 2025 年树脂排水沟厂家 TOP 品牌权威排行榜单,U 形、线性、成品、混凝土、园林、市政、玻璃钢树脂排水沟公司推荐
  • 2025 年石墨烯厂家推荐 TOP 品牌排行榜单最新发布,氧化 / 羧基化 / 巯基化 / 羟基化 / 氨基化 / 氮掺杂氧化 / 氮掺杂石墨烯公司推荐
  • AtCoder Grand Contest 015 - E - Mr.Aoki Incubator
  • 9.30 CSP-S模拟25 改题记录
  • 全球抗体药表达系统:CHO 细胞主导下,未来十年将迎哪些突破?
  • 完整教程:[论文阅读]Benchmarking Poisoning Attacks against Retrieval-Augmented Generation
  • 绕过Cloudflare IP白名单限制的技术解析
  • 撕裂的乡土:在人性荒原上寻找微光
  • 2025蔬菜配送服务公司 TOP 企业推荐排行榜,深圳、宝安、光明、松岗、东莞、长安、虎门、沙田、厚街、大岭山蔬菜配送推荐
  • 2025液压缸TOP企业品牌推荐排行榜!抓斗、伺服、大吨位、车辆、工程、拉杆、冶金、重载、港机液压缸推荐
  • 2025 年破胶机厂家品牌推荐榜单白皮书,多规格型号 610/710/810、大型、自动型、低温环保、节能省电、自动打块、轮胎破胶机公司推荐
  • 乱七八糟的国庆做题记录
  • 2025 年健身器材品牌 TOP 推荐排行榜,室内 / 健身房 / 体育 / 运动 / 家用 / 商用 / 单位 / 家庭 / 有氧 / 力量健身器材推荐
  • 详细介绍:给贾维斯加“手势控制”:从原理到落地,打造多模态交互的本地智能助
  • 完整教程:学术论文 Word 样式规范
  • 取印度孟买指数(SENSEX)实时行情API对接指南
  • 2025青海视频号运营优质公司推荐榜:专业服务与创新策略口碑
  • 2025 年发泡陶瓷厂家 TOP 企业品牌推荐排行榜,发泡陶瓷线条 / 构件 / 装饰构件 / 空心砖 / 窗套线 / 浮雕 / 装饰线条推荐这十家公司
  • Future相关并发类使用
  • 2025 年传感器厂家 TOP 企业品牌推荐排行榜,磁致伸缩 / 防爆 / 防水 / 隔爆 / 线性 / 矿用 / 直线 / 油缸位移传感器 / 液位传感器公司推荐!
  • 2025 年热转印花膜厂家 TOP 企业品牌推荐排行榜,硅胶 / 五金 / 塑胶 / ABS / 涂料桶 / PP / 水杯 / 温变 / 冰变热转印花膜加工厂推荐
  • 2025 年生物除臭设备厂家 TOP 品牌企业推荐排行榜揭晓:印染厂污水 / 食品厂污水 / 污水处理厂 / 污水泵站 / 污水站 / 餐厨垃圾 / 屠宰场 / 厨余垃圾生物除臭设备公司推荐
  • JUC:读写锁
  • 2025 年舞台厂家 TOP 品牌企业权威推荐榜单,铝合金舞台、活动舞台、快装舞台、舞台架、折叠舞台、演出舞台、演唱会舞台桁架、舞台设计公司推荐
  • 2025 年点胶机厂家 TOP 企业推荐排行榜,自动 / 果冻胶 / 无痕内衣 / 烫钻 / 珠宝热熔胶 / 水钻热熔胶 / 亮片热熔胶 / 金葱粉热熔胶点胶机推荐这十家公司!
  • 2025 年知识库应用工具系统平台推荐排行榜,企业 / 行业 / 专家 / 问答 / 智能 / 培训 / 协同 / 办公 / 内部 / 外部 / 个人 / 客服 / 营销知识库应用软件推荐!
  • 2025 年移民服务公司性价比排行:美国、加拿大等国 TOP 机构,综合费用与服务质量的考量!
  • 2025 年水泥墩公司推荐最新榜单白皮书发布,圆形 / 方形 / 光伏水泥墩 / 围挡水泥墩 / 护栏水泥墩 / 交通水泥墩 / 防撞水泥墩源头厂家推荐