哈希亂搞：CF1418G Three Occurrences
這道題看起來(lái)并不是那么好做，看到題解神秘做法，記錄下來(lái)。
考慮枚舉右端點(diǎn)，統(tǒng)計(jì)符合條件的左端點(diǎn)數(shù)量。
發(fā)現(xiàn) 3 這個(gè)數(shù)字很小，發(fā)現(xiàn)區(qū)間中的數(shù)我們僅僅需要知道它 %3 的值。
我們?nèi)绻梢杂涗浺粋€(gè)位置前綴中所有值的出現(xiàn)情況就好了，但是明顯不現(xiàn)實(shí)，整個(gè)數(shù)據(jù)是 \(n^2\) 級(jí)別的。
就算我們搞一棵主席樹，似乎也沒(méi)有什么可以快速確定左端點(diǎn)的方式。
如果我們可以把一大堆數(shù)的出現(xiàn)次數(shù)壓成一坨，并且這一坨還可差分就好了。
想到了集合哈希。
我們給每一個(gè)數(shù)一個(gè)隨機(jī)值，每個(gè)位置的哈希值就是出現(xiàn)次數(shù) %3 乘上隨機(jī)值。
不難發(fā)現(xiàn)兩個(gè)位置如果哈希值是相等的，那么區(qū)間就是合法的。
但是這個(gè)辦法有一個(gè)問(wèn)題：沒(méi)有辦法保證恰好出現(xiàn)了 3 次。
我們考慮雙指針，每次向右移動(dòng)右端點(diǎn)，維護(hù)左端點(diǎn)，顯然左端點(diǎn)只會(huì)向右。
就沒(méi)有了↓
點(diǎn)擊查看代碼
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int MN=1e6+116;
int n, a[MN], cnt[MN], ans=0;
unordered_map <int, ull> trans;
map <ull, int> mp;
ull hashed[MN];
signed main(){
mt19937_64 rnd(114514);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n; for(int i=1; i<=n; ++i) trans[i]=rnd();
for(int i=1; i<=n; ++i){
hashed[i]=hashed[i-1]; cin>>a[i];
hashed[i]-=cnt[a[i]]*trans[a[i]];
++cnt[a[i]]; cnt[a[i]]%=3;
hashed[i]+=cnt[a[i]]*trans[a[i]];
}
mp[0]=1; memset(cnt,0,sizeof(cnt));
for(int i=1,j=0; i<=n; ++i){
++cnt[a[i]];
while(cnt[a[i]]>3){
--cnt[a[j]];
if(j) --mp[hashed[j-1]];
++j;
}
ans+=mp[hashed[i]];
++mp[hashed[i]];
}
cout<<ans<<'\n';
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)