20AB-day3 Good Subsegments
题意
给你一个长度为 \(n\) 的序列 \(a\)，问有多少个子区间，满足 \(\sum_{i=l}^r 2^{a_i}=2^x\)，其中 \(x\) 为非负整数。
原题解
第一个想法：若 \(2^{a_l}+2^{a_{l + 1}}+\cdots +2^{a_r}=2^x\)，则 \(x\le \max(a_l,a_{l + 1},\cdots,a_r)+\log n\)。
第二个想法：为检验 \(2^{a_l}+2^{a_{l + 1}}+\cdots +2^{a_r}=2^x\)，可使用若干随机素数 \(p\) 并检验 \(2^x\bmod p\) 是否等于下面的和对 \(p\) 取模所得结果。
第三个想法：可使用分治算法，假设最大值在右侧，对于固定的 \(r\)，存在 \(l\) 的某个后缀，其中最大值等于 \(\max(a_m,a_{m + 1},\cdots,a_r)\)。可确定 \(x\)（仅有 \(\log\) 种可能），然后需检验在给定后缀上是否存在模 \(p\)（对于若干不同的 \(p\)）的所需和。使用哈希表可在 \(O (1)\) 时间内进行检验。
总复杂度为 \(O (n\log^2 n)\)。
思路
首先有原题解的结论：若 \(2^{a_l}+2^{a_{l + 1}}+\cdots +2^{a_r}=2^x\)，则 \(x\le \max(a_l,a_{l + 1}, \cdots,a_r) + \log n\)。
一个想法是预处理前缀和，然后对于每个 \(l\)，枚举 \(x\)，计算有多少个 \(r\) 满足 \(s_l+2^x=s^r\)。
因为前缀和不好记录，我们可以考虑哈希来判断，判断是 \(O(1)\)。
不喜欢题解的分治做法，感觉笛卡尔树启发式合并的做法更加优美。
对于一个区间最大值，考虑把它的左边或者右边插入哈希表，然后枚举没有插入哈希表的一边，然后枚举每一个 \(x\)，然后在哈希表查询满足等式的点的数量。
但是笛卡尔树最坏深度是 \(O(n)\)，因此考虑启发式合并，每次合并大的儿子的哈希表，删除小儿子的哈希表，然后枚举小儿子的结点。有一些加减 \(1\) 的细节很讨厌。
时间复杂度是 \(O(n \log^2 n)\) 的。要手写哈希表qwq。
怎么还要卡常？
过哩！其实题目不用卡常，是我复杂度写假了，快速幂多叠了一个 log
code
感觉有点难写。
#include<bits/stdc++.h>
#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=2e5+7;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T >
inline void read(T & x) {
x=0;
T fl=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fl=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
x=x*fl;
}
int n;
int a[N];
ll ans;
const int mod1=1e9+103,mod2=1e9+123;
typedef pair<int,int> pii;
#define fi first
#define se second
pii ksm(ll a,ll b) {
ll s1=1,s2=1;
ll a1=a,a2=a;
while(b) {
if(b&1) s1=s1*a1%mod1,s2=s2*a2%mod2;
a1=a1*a1%mod1;a2=a2*a2%mod2;
b>>=1;
}
return {s1,s2};
}
int add1(int a,int b) { return a+b>=mod1?a+b-mod1:a+b; }
int add2(int a,int b) { return a+b>=mod2?a+b-mod2:a+b; }
int s1[N][20],s2[N][20];
const int sz=1e7+103;
struct _hash{
int head[sz];
int f(pii key) {
return (key.fi+key.se)%sz;
}
struct _map {
pii val;
int key;
int num;
int ne;
}mp[N];
int cnt;
void clear() {
while(cnt) head[mp[cnt--].key]=0;
}
int find(pii key) {
int h=f(key);
for(int i=head[h];i;i=mp[i].ne) if(mp[i].val==key) return i;
return 0;
}
void insert(pii key) {
int h=f(key);
int it=find(key);
if(it) mp[it].num++;
else mp[++cnt]={key,h,1,head[h]},head[h]=cnt;
}
int operator [] (int it) const { return mp[it].num; }
}hashmp;
int st[N][20];
int _max(int x,int y) { return a[x]>a[y] ? x : y; }
int getmax(int l, int r) {
int lg=__lg(r-l+1);
return _max(st[l][lg],st[r-(1<<lg)+1][lg]);
}
const int lgg=20;
void solve(int l, int r) {
if(l>r) {
hashmp.insert({s1[l-1][0],s2[l-1][0]});
return;
}
int rt=getmax(l,r);
if(rt-l>r-rt) {
solve(rt+1,r);
hashmp.clear();
solve(l,rt-1);
rep(i,rt,r) {
rep(x,a[rt],a[rt]+lgg-1) {
auto ss=ksm(2,x);
pii key={add1(mod1-ss.fi,s1[i][0]),add2(mod2-ss.se,s2[i][0])};
int it=hashmp.find(key);
if(it) ans+=hashmp[it];
}
}
rep(i,rt,r) hashmp.insert({s1[i][0],s2[i][0]});
}else {
solve(l,rt-1);
hashmp.clear();
solve(rt+1,r);
rep(i,l-1,rt-1) {
rep(x,a[rt],a[rt]+lgg-1) {
auto ss=ksm(2,x);
pii key={add1(ss.fi,s1[i][0]),add2(ss.se,s2[i][0])};
int it=hashmp.find(key);
if(it) ans+=hashmp[it];
}
}
rep(i,l-1,rt-1) hashmp.insert({s1[i][0],s2[i][0]});
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my4.out","w",stdout);
#endif
read(n);
rep(i,1,n) {
st[i][0]=i;
read(a[i]);
pii x=ksm(2,a[i]);
s1[i][0]=add1(s1[i-1][0],x.fi);
s2[i][0]=add2(s2[i-1][0],x.se);
rep(k,1,lgg-1) s1[i][k]=add1(s1[i][k-1],s1[i][k-1]),s2[i][k]=add2(s2[i][k-1],s2[i][k-1]);
}
int lg=__lg(n+1);
rep(k,1,lg) {
for(int i=0;i+(1<<k)-1<=n;i++) {
st[i][k]=_max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
}
solve(1,n);
pf("%lld\n",ans);
}