menu zcmimi's blog

arrow_back rmq

有多种做法

AC自动机暴力

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

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

AC自动机暴力

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

对点名串建立AC自动机

zc
2020-05-17 16:09

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

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

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

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

解↓决↑! ```

zc
2020-01-18 22:40

kruskal重构树模板 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define i
zc
2019-12-31 11:31

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

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

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

看到这句话了没?

所以不用考虑分治是

zc
2019-12-21 19:47

二分

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

include<bits/stdc++.h>

namespace ZDY{

#pragma G
zc
2019-12-21 19:47

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

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

至于求$gcd(a_l,...,a_r),or(

zc
2019-12-21 19:47

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

然后rmq预处理

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

注意多组数据

```cpp

include<bits/stdc+

zc
2019-12-21 19:47
1 / 1
Search
search