Wannafly Winter Camp 2020 Day 6H 异或询问

给定一个长 \(n\) 的序列 \(a_1,\dots,a_n\)，定义 \(f(x)\) 为有多少个 \(a_i \leq x\)

有 \(q\) 次询问，每次给定 \(l,r,x\)，求 \(\sum_{i=l}^r f(i \ xor\ x)^2\)

Solution

定义 \(S*x={y \ xor \ x|y \in S}\)，\((x)_i\) 表示 \(x\) 第 \(i\) 位的值，则所求为 \(\sum_{y\in[L,R]*x} f^2(y)\)，差分一下，只需要求 \(\sum_{y\in[0,R]*x} f^2(y)\)

手玩一下可以想到， \([0,R]*x\) 一定能被划分为 \(O(\log n)\) 个连续的区间

考虑第 \(w\) 位

如果 \(R<2^w\)，若 \((x)_w=0\) 则变为 \([0,R]*x'\)，若 \((x)_w=1\) 则变为 \([2^w,2^w+R]*x'\)，其中\(x'=x \& (2^w-1)\)
如果 \(R\geq 2^w\)，若 \((x)_w=0\) 则变为 \([0,2^w-1] + [2^w,R]*x'\)，后者递归下去即可；若 \((x)_w=1\) 则变为 \([2^w,2^{w+1}-1] + [0,R-2^w]*x'\)，后者同样递归做下去

如果我们能快速完成这种划分，那么问题转化为求 \(g(R)=\sum_{x\leq R} f^2(x)\)，考虑到这个函数是个分段线性函数，不妨假设 \(a_i\) 已经排序，我们只需要预处理出序列 \(g(a_1),g(a_2),\dots, g(a_n)\)，那么询问时拿着 \(R\) 在 \(a\) 序列上二分一下，就可以很容易算出答案。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100005;

const int mod = 998244353;

struct range{int l,r;};

vector<range> xorrange(int r,int x) {

    vector <range> v;

    v.push_back({r^x,r^x});

    int offset=0;

    for(int i=30;i>=0;--i) {

        if(r<(1<<i)) {

            if(x&(1<<i)) {

                offset+=(1<<i);

            }

        }

        else {

            if(x&(1<<i)) {

                v.push_back({(1<<i)+offset,(1<<(i+1))-1+offset});

                r^=(1<<i);

            }

            else {

                v.push_back({offset,(1<<i)-1+offset});

                r^=(1<<i);

                offset+=(1<<i);

            }

        }

        x&=(1<<i)-1;

    }

    return v;

}

int n,q,a[N],f[N],g[N];

int calc(int x) {

    int p = upper_bound(a+1,a+n+1,x) - a-1;

    return (g[p] + (x-a[p])*p*p) % mod;

}

int gen(int p,int x) {

    vector<range> v=xorrange(p,x);

    int ans=0;

    for(int i=0;i<v.size();i++) ans+=(calc(v[i].r)-calc(v[i].l-1)+mod)%mod,ans%=mod;

    return ans;

}

signed main() {

    ios::sync_with_stdio(false);

    cin>>n>>q;

    for(int i=1;i<=n;i++) cin>>a[i];

    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++) g[i]=(g[i-1]+(i-1)*(i-1)%mod*(a[i]-a[i-1]-1)+i*i)%mod;

    for(int i=1;i<=q;i++) {

        int l,r,x;

        cin>>l>>r>>x;

        cout<<(gen(r,x)-gen(l-1,x)+mod)%mod<<endl;

    }

}

巴特西

Wannafly Winter Camp 2020 Day 6H 异或询问 - 二分

Solution

最新文章

热门文章