算竞笔记 - 哈希类型专题
1. Candy Rush TL;DR - 串哈希加速比对 + big hash trick 2023-2024 ACM-ICPC Latin American Regional Programming Contest 官方题解：https://codeforces.com/gym/104736/attachments/download/22730/editorial.pdf 取$C_i$出现频率为向量做前缀和后可发现有效区间频率差为$k \cdot 1_n$；直接比对平摊复杂度为$O(nk\log{n})$,$O(k)$来自于比对本身 而比对可以转换为$O(1)$形式，trick如下： 若 $a,b$ 对应区间有效，一定有：$freq_b = k \cdot 1_n + freq_a$ 而在做前缀和是，可以及时消掉$k \cdot 1_n$项：即为全非$0$时全$-1$ 此时的比对即变成$ hash(freq_b) = hash(freq_a) $ 造一个能$O(1)$更新的$hash$即可让最终复杂度可以变为优秀的$O(nlogn)$ 题解$hash$为$(base^i \cdot c_i)%MOD$ - 避免碰撞可以采用更大int类型或模数，或同code开array于不同base计算后比较 #pragma GCC optimize("O3","unroll-loops","inline") #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef __int128 i128; typedef unsigned __int128 ui128; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin....