CSP 模拟 46

Ishar-zdl的博客 / 2024-10-13 / 原文

A

二分答案，每个数去找范围内最左边的。

B

相同的数不会交换，所以设 $f_{i,j,k,u}$ 为到 $i$，有了 $j$ 个 0，$k$ 个 1，当前位置是 $u$ 的最小代价，转移是暴力的，如果一个数要去前面，那么最优的方案一定不会把他往后面换，所以两次移动只有一次贡献，最终的答案要除以 $2$。

C

首先有双指针的暴力，然后基于这个就可以在线段树上合并了。

D

首先有最大值固定的一个部分分，这一档使用 trie 树，然后经典问题找最大值覆盖的所有区间，每次去遍历小的那一半就是 $\mathcal{O}(n\log n)$，然后还是用部分分的思路，但是只能以固定区间的数作为节点点，所以上可持久化 trie 树，时间复杂度 $\mathcal{O}(n\log n\log a)$。

#include<bits/stdc++.h>
// #define int long long
#define pii std::pair<int,int>
#define eb emplace_back
#define fo(i,s,t) for(int i=s;i<=t;++i)
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,inf=2e9;
int n,a[N],root[N],tr[N<<5][2],sum[N],sz[N<<5],la[N<<5],tot,s[N],top,L[N],R[N];
ll ans;
inline void insert(int last,int p,int x,int rnk){
    for(int i=30;~i;--i){
        tr[p][0]=tr[last][0],tr[p][1]=tr[last][1];
        int z=(x>>i)&1;
        tr[p][z]=++tot;p=tot;
        last=tr[last][z];sz[p]=sz[last]+1;la[p]=rnk;
    }
}
inline int query(int l,int last,int p,int x,int li){
    int res=0;
    for(int i=30;~i;--i){
        int o1=(li>>i)&1,o2=(x>>i)&1;
        if(o1)res+=sz[tr[p][o2]]-sz[tr[last][o2]],o2^=1;
        if(tr[p][o2]&&la[tr[p][o2]]>=l)p=tr[p][o2],last=tr[last][o2];
        else {last=p=0;break;}
    }
    return res+sz[p]-sz[last];
}
signed main(){
    freopen("xor.in","r",stdin);freopen("xor.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();for(int i=1;i<=n;++i)a[i]=read(),sum[i]=sum[i-1]^a[i];
    insert(0,root[0]=++tot,0,0);for(int i=1;i<=n;++i)insert(root[i-1],root[i]=++tot,sum[i],i);
    a[0]=inf;s[++top]=0;for(int i=1;i<=n;++i){
        while(a[s[top]]<a[i])--top;
        L[i]=s[top]+1;s[++top]=i;
    }top=0;a[n+1]=inf;s[++top]=n+1;
    for(int i=n;i;--i){
        while(a[s[top]]<=a[i])--top;
        R[i]=s[top]-1;s[++top]=i;
    }
    for(int i=1;i<=n;++i){
        if(i-L[i]+1<R[i]-i+1){
            int l=i,rt=root[l-1];
            for(int j=L[i]-1;j<i;++j)ans+=query(l,rt,root[R[i]],sum[j],a[i]);
        }else{
            int l=L[i]-1,rt;
            if(!l)rt=0;else rt=root[l-1];
            for(int j=i;j<=R[i];++j){
                ans+=query(l,rt,root[i-1],sum[j],a[i]);
            }
        }
    }
    std::cout<<ans<<'\n';
}