题解：AT_arc216_c [ARC216C] Count Power of 2

· · 题解

~易得~性质一：一段区间的和最多不会超过 mx+\log n，其中 mx 是输入序列的区间最大值。

于是我们建出笛卡尔树，考虑在笛卡尔树上分治。令 b_i=2^{a_i},pre_i=\sum_{j=1}^{i} b_j。

因为笛卡尔树上的一个点代表一段区间的最大值，所以我们考虑包含该最大值的合法区间的个数，枚举最终的区间和 B。根据性质一，mx\le \log_2 B \le mx+\log_2 n，所以枚举 B 是 O(\log n) 的。这时我们有两种维护包含该最大值合法区间的方法：

直接做是 O(n^2 \log n) 的。

我们可以用启发式来优化，只枚举短的一边，另外一边通过递归放入 unordered_map 里。这样时间复杂度就优化到 O(n\log^2 n) 了。

对于 pre_i 的维护：我们肯定维护不了 2^{2\times 10^5}，用个 10^{18} 级别的质数取模，或双模处理。(1e9+7 级别的单模，哈希冲突概率高达 1/10)

为了防止出题人卡我们的 unordered_map 导致我们 TLE，可以把插入和查询的值先乘上一个值再加上一个值，两个值可以在程序初始化时随机一下。

:::success[代码]

#include<bits/stdc++.h>
#define fi first
#define se second
#define pi pair<int,int>
typedef long long ll;
using namespace std;
const int N=2e5+100;
const int mod[2]={998244353,(int)1e9+9};
struct node{
    ll fi,se;
    ll lld(){
        return (fi<<32)|se;
    }
    static ll ck0(ll x,ll y){
        x+=y;
        if(x<0) x+=mod[0];
        if(x>mod[0]) x-=mod[0];
        return x;
    }
    static ll ck1(ll x,ll y){
        x+=y;
        if(x<0) x+=mod[1];
        if(x>mod[1]) x-=mod[1];
        return x;
    } 
    node operator+(const node &X)const{
        return {ck0(fi,X.fi),ck1(se,X.se)};
    }
    node operator-(const node &X)const{
        return {ck0(fi,-X.fi),ck1(se,-X.se)};
    }
    bool operator==(const node &X)const{
        return fi==X.fi&&se==X.se;
    }
    node operator*(const ll &X)const{
        return {fi*X%mod[0],se*X%mod[1]};
    }
    node operator*(const node &X)const{
        return {fi*X.fi%mod[0],se*X.se%mod[1]};
    } 
};
int n;
ll a[N];
node b[N],pre[N];
ll ans;
int l[N],r[N],st[N],top;
int root;
struct CustomHash {
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = 
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
unordered_map<ll,int,CustomHash> mp;
node qmi(node x,ll y){
    node res={1,1};
    while(y){
        if(y&1) res=res*x;
        x=x*x; y>>=1;
    }
    return res;
}
void build(){
    for(int i=1;i<=n;i++){
        int last=0;
        while(top&&a[st[top]]<a[i]) last=st[top],top--;
        if(top) r[st[top]]=i;
        else root=i;
        l[i]=last;
        st[++top]=i;
    }
}
void dfs(int u,int tl,int tr,bool is=false){
    if(!u) return ;
    if(tr-u<u-tl){
        dfs(r[u],u+1,tr,0);
        dfs(l[u],tl,u-1,1);
        node bas=b[u];
        mp[pre[tl-1].lld()]++;
        for(int s=0;s<=20;s++){
            for(int i=u;i<=tr;i++){
                node t=pre[i]-bas;
                if(mp.find(t.lld())!=mp.end())
                    ans+=mp[t.lld()];
            }
            bas=bas*2;
        }
        mp[pre[tl-1].lld()]--;
        for(int i=u;i<=tr;i++) mp[pre[i].lld()]++;
    }else{
        dfs(l[u],tl,u-1,0);
        dfs(r[u],u+1,tr,1);
        node bas=b[u];
        mp[pre[u].lld()]++;
        for(int s=0;s<=20;s++){
            for(int i=tl;i<=u;i++){
                node t=pre[i-1]+bas;
                if(mp.find(t.lld())!=mp.end())
                    ans+=mp[t.lld()];
            }
            bas=bas*2;
        }
        mp[pre[u].lld()]--;
        for(int i=tl;i<=u;i++) mp[pre[i].lld()]++;
    }
    if(!is) mp.clear();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=qmi({2,2},a[i]);
    }
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+b[i];
    build();
    dfs(root,1,n);
    cout<<ans;
    return 0;
}

:::