自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:40:14，当前版本为作者最后更新于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;
}