疯狂匹配题解

首先我们可以求出从每个L开始匹配，失配前最后一个匹配的位置，这个位置+1就是下一次匹配开始的位置，并且记录下来。
这一步用二分+哈希即可。
有了上面求的这个东西，我们就可以倍增了，用ST表存下L出发走2的次幂步能到的最后一个位置。
对于每一个询问，直接用倍增数组跳就好了。
这样记录从0出发的次数也很容易，就相当于是失配次数。
至于结束位置，可以用哈希+map来存储。
最终总复杂度为O(qlogm)

全部评论

相关推荐

头像
刻苦的安哥拉兔在学习
05-07 10:11
门头沟学院 计算机类
点赞 评论 收藏
转发
头像
在吃瓜的青提很用心
05-09 11:52
博世_视觉算法工程师(准入职员工)
博世暑期实习内推
博世24届春招补招内推大家好！全球100强企业——博世中国开始秋招啦！25届也可以用这个内推码，大家可以收藏一下。关键词：外企 大厂 WLB你是否渴望工作生活平衡的工作，你是否想加入跨国公司与全球各地的伙伴一起协作，你是否想加入一家百年企业感受永不上市的文化。这里就是博世！欢迎你的加入！作为校招加入博世的应届生，当时最打动我的还是招聘者的一句话：博世是一家注重长远利益的公司，我们有时间等你慢慢成长！确实，入职以来，听到最多的是“合规”，创始人罗伯特·博世的“宁失利，勿失信”令我印象深刻。作为全球汽车供应商的龙头老大，博世在汽车零部件、家电、电动工具、能源与互联网方面都颇有建树，当然，作为一家不...
点赞 评论 收藏
转发
头像
Stupid_Pig
03-30 10:54
广州应用科技学院 计算机类
点赞 评论 收藏
转发
头像
为霞_尚满天
04-20 19:39
辽宁工程技术大学 计算机类
点赞 评论 收藏
转发
头像
泥电第一华孝子
昨天 21:02
电子科技大学 计算机类
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
660574次浏览 10930人参与
# 无实习如何秋招上岸 #
212946次浏览 3313人参与
# 你的简历改到第几版了 #
295811次浏览 4477人参与
# 23届的你们都什么时候入职？ #
83347次浏览 724人参与
# 租房前辈的忠告 #
31004次浏览 2025人参与
# 找工作中的意难平 #
184302次浏览 3340人参与
# 硬件人的简历怎么写 #
76245次浏览 775人参与
# 华为开奖那些事 #
694666次浏览 5969人参与
# 简历中的项目经历要怎么写 #
422143次浏览 7176人参与
# 机械人怎么评价今年的华为 #
65876次浏览 531人参与
# 秋招开了，你想投哪些公司呢 #
115079次浏览 3234人参与
# 五一之后，实习真的很难找吗？ #
16843次浏览 105人参与
# 我想象的工作vs实际工作 #
90098次浏览 1523人参与
# 金融银行面经 #
4693次浏览 104人参与
# 你投了多少份简历，才拿到offer？ #
5293次浏览 59人参与
# 你已经投递多少份简历了 #
286040次浏览 4336人参与
# 第一份工作应该选择高薪还是大平台 #
33724次浏览 252人参与
# 本周投递记录 #
194220次浏览 5014人参与
# 工作压力大怎么缓解 #
9716次浏览 135人参与
# 打工人的辛酸 #
8056次浏览 113人参与
牛客网
牛客企业服务