题解：P17723 [SCP-S 2026] 函数 / func

· · 题解

题解：P17723 [SCP-S 2026] 函数 / func

这道题真不错吧……

注：题解使用 AI 进行学术性检查和笔误检查，所有文本皆本人所写，贡献为 AI 的三倍以上。

part 1：

首先，对于一段区间 [l,r]，令 S=\{a_l,a_{l+1},\cdots,a_{r-1},a_r\}。 令 \operatorname{MEX}(S) 为 m，我们能够发现，序列中肯定包含有 0 到 m-1 的所有数，然而我们真正需要关心的是 \operatorname{OR}(S)\mid m 是否等于 \operatorname{OR}(S)。由于 \operatorname{OR}(S) 包含 0 到 m-1 的按位或，所以只需在意 0 到 m-1 的按位或是否覆盖了 m 的所有 1 位。我们很容易看出，只有当 m 的二进制中存在满足 m 在该位为 1 而 0 到 m-1 的所有数在该位都不为 1 才能满足条件，显然，只有当 m 为 2 的非负整数次幂时才能满足此条件。我们来证明一下：

所以答案就被拆成了两个部分：所有区间的按位或的和、部分 \operatorname{MEX} 所产生的贡献（具体见 part 2）。

part 2：

那么哪些区间会对答案产生贡献呢？

由 part 1 可知，只有当 \operatorname{MEX}(S)=2^k 且 \operatorname{OR}(S) 的第 k 位为 0 时，\operatorname{OR}(S)\mid \operatorname{MEX}(S) 才会比 \operatorname{OR}(S) 多出 2^k。也就是说，对于每个 k，我们需要统计同时满足以下两条的区间 [l,r]：

  1. 这一段区间的所有数二进制的第 k 位都为 0（保证有贡献）；
  2. 区间包含 0 到 2^k-1 的所有数（保证 \operatorname{MEX}(S)=2^k）。

于是问题变成了：对每个 k，统计第 k 位全为 0 且包含 0 到 2^k-1 所有数的区间个数，乘以 2^k 累加就是这一部分的答案。

如何统计？观察到第 k 位必须为 0，所以我们可以以第 k 位为 1 的数做分割，将数组分成多个区间，显然合法区间不能超出这些区间。我们在每个合法段内统计，从左往右遍历右端点，找到最短合法区间，以便结合最长合法区间（左端点抵在合法段的最左侧的区间）算出合法区间数量，为了满足第二个条件，我们可以维护每一个小于 2^k 的数（条件所要求的必要值）最后出现的下标 pre，用桶 t 来维护每个值出现的次数，从而判断它是否第一次出现。可以使用队列按位置顺序维护每个必需值最后一次出现的位置；当某个值再次出现时，旧位置就会成为过期元素，之后通过不断检查队首将过期队首弹出（为了满足合法区间最小）。这样队列中每个必需值只保留最后一次出现的位置，且按位置升序排列，因此队首就是所有必需值最后出现位置中的最小值，答案便是合法区间数量乘 2^k，累加后就是部分 \operatorname{MEX} 所产生的贡献。

part 3：

我们该如何计算所有区间的按位或的和呢？我们能够发现按位或运算每一位都是独立的，所以我们每一位进行计算就可以了。

对于第 k 位，一个区间的按位或在第 k 位为 1，当且仅当这个区间里至少存在一个数的第 k 位为 1，但是这不好统计啊，但是我们可以反过来统计：用总区间数减去区间内所有数的第 k 位都为 0 的区间数，第 k 位全为 0”的区间，只可能出现在若干个连续的 0 段内部，对于一个长度为 L 的区间，那么其中全 0 子区间数就有 \frac{L(L+1)}{2} 段区间，所以可以直接扫过去，然后在分割点和末尾计算前一段的区间的区间数就可以了。设第 k 位按位或为 0 的区间数为 cnt，则第 k 位对答案的贡献就是 \left(\frac{n(n+1)}{2}-cnt\right) \cdot 2^k。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+111;
int a[N];
int n;
int pre[N];
int t[N];
signed main(){
//  freopen("func.in","r",stdin);
//  freopen("func.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    unsigned long long ans=0;
    for(int i=0;i<=31;i++){
        int top=0;
        unsigned long long cnt=0;
        for(int j=1;j<=n;j++){
            if(a[j]&(1ll<<i)){
                cnt+=(j-1-top)*1llu*(j-top)/2;
                top=j;
            }
        }
        if(top==0){
            continue;
        }
        cnt+=(n+1-top)*1llu*(n-top)/2;
        ans+=((n+1)*1llu*n/2-cnt)*1llu*(1ll<<i);
    }
    queue<int>q;
    for(int i=0;i<=20;i++){//log N
        while(!q.empty()){
            pre[a[q.front()]]=0;
            t[a[q.front()]]--;
            q.pop();
        }
        int top=0;
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(a[j]&(1<<i)){
                while(!q.empty()){
                    pre[a[q.front()]]=0;
                    t[a[q.front()]]--;
                    q.pop();
                }
                cnt=0;
                top=j;
                continue;
            }
            if(a[j]<(1<<i)){
                q.push(j);
                pre[a[j]]=j;
                if(t[a[j]]==0){
                    cnt++;
                }
                t[a[j]]++;
            }
            while((!q.empty())&&pre[a[q.front()]]>q.front()){
                t[a[q.front()]]--;
                q.pop();
            }
            if(cnt<(1<<i)){
                continue;
            }
//          cerr<<i<<" "<<j<<" "<<q.front()<<" "<<top<<"\n";
            ans+=(q.front()-top)*1llu*(1<<i);
        }
    }
    printf("%llu",ans);
    return 0;
}

感谢你的观看，芜湖。