P8569 [JRKSJ R6] 第七学区

Rainbow_qwq · 2022-07-30 23:46:54 · 题解

来写一下 n\log n 做法。

首先要有一个 n\log V 的 simple 做法。考虑对于每个位，数 0 段的个数，然后用全部的减去这些。对每个位维护一个 lst_i 表示当前结尾有多少个 0，那么这个位下一次是 0 就是操作 lst_i\to lst_i+1,sum\to sum+2^i，否则是 lst_i\to 0,sum\to sum-lst_i2^i。可以写出如下代码。

int n;
ull res,lst[66];
inline ull C2(int x){return 1ull*x*(x-1)/2;}

signed main()
{
    READ::init(n);
    ull sum=0;
    int lim=0;
    For(i,0,n-1){
        ull x=READ::read();
        sum+=(~x);
        For(j,0,63)
            if(x>>j&1)sum-=lst[j]<<j,lst[j]=0;
            else ++lst[j];
        res-=sum;
    }
    res-=C2(n+1);
    cout<<res;
    return 0;
}

用一个 trick，考虑原本我们维护的是 64 个 lst_j，且 lst_j 是 \le n 的，把二进制数位画出来，这是一个 01 矩阵，并且只有 64\times \log n 个位置可能有值。于是考虑转置这个矩阵，维护 w_i 表示哪些 lst_j 的第 i 位为 1，这样只需要维护 \log n 个 w_i。

对于 lst_i\to 0 的操作就是把 w_i 的那些位变为 0；对于 lst_i\to lst_i+1 的操作就手动模拟二进制加法器。代码如下。

小常数 n\log n，1.6s。

int n;
ull res;

inline ull C2(int x){return 1ull*x*(x-1)/2;}
ull w[30];

signed main()
{
    READ::init(n);
    ull sum=0;
    int lim=0;
    For(i,0,n-1){
        ull x=READ::read();
        sum+=(~x);
//      For(j,0,63)
//          if(x>>j&1)sum-=lst[j]<<j,lst[j]=0;
//          else ++lst[j];
        ull up=(~x),nup;
        for(int j=0;j<=lim;++j){
            sum-=(w[j]&x)<<j;
            w[j]&=(~x); // 上两行是变为 0 的操作
            nup=up&w[j];
            w[j]^=up;
            up=nup; // 上三行是模拟 +1 的二进制加法器
        }
        if((i&-i)==i)++lim;
        res-=sum;
    }
    res-=C2(n+1);
    cout<<res;
    return 0;
}