zcmimi's blog

arrow_backrmq共7篇文章

avatar
zc
2020-05-17 16:09:00
查看原题

点击跳转

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先rmq预处理出区间gcd和区间min

若区间gcd=区间min那么这个区间是合法的

若一个区间合法,那么它一定有合法的子区间

我们可以根据这个性质二分区间长度

解↓决↑!

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

kruskal重构树模板

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以用分治愉快的解决这道题

答案统计的时候记得开long\ long

由于某种不可抗力,ai的值将会是1~10^9内随机的一个数。(除了样例)

看到这句话了没?

所以不用考虑分治是否会tle

不过我加了个rmq,就算没有这句话也可以过

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先预处理出以i结尾最长多少个连续

然后rmq预处理

查询的时候要先查以左端点开始最长多少,然后再求剩下的那段区间

注意多组数据

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分

判断的时候枚举区间,用rmq或单调队列来求最值,还可以用堆(看题解的)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以发现gcd(a_l,...,a_r)是单调递减的,而or(a_l,...,a_r)是单调递增的

所以我们可以两次二分来找到合法区间

至于求gcd(a_l,...,a_r),or(a_l,...,a_r)我们可以用rmq来求

1/1
Search
search