莫队二次离线（第十四分块前体）

莫队二次离线

核心部分

依然是按正常的莫队思想，首先考虑一种情况，即：考虑区间从 \([l,r]\) 变为了 \([l,r+1]\)

设 \(f(v,S)\) 表示位置 \(v\) 对区间 \(S\) 的贡献

那么新增加的贡献就是

直接计算是不行的，我们需要挖掘更多的性质

异或是可以前缀和的，所以我们将上面的式子拆开

不难发现左边的式子是一个数对其前面的所有数的贡献，第一次离线时即可计算

重点是我们如何计算后面的式子

后面的式子也不是没有特点，我们发现这都是求一个数对一个固定区间的贡献

于是我们在一次离线时保存一下，第二次离线时计算即可

综上，我们来讨论一下莫队的四种情况

以下设 \(l,r\) 表示询问的区间，\(L,R\) 表示上一次更新完毕后的左右指针的位置

• \(L>l\)：也就是说 \(L\) 在 \(l\) 的右面，向左移动

每次增加的贡献是：

后面的式子我们偷个懒，将其化为 \(f(L-1,[1,L-2])\)

然后我们第一次离线能计算的是后面那一堆，所以是不断进行减法操作

最后我们在 \(R\) 的位置保存第二次离线要进行计算的东西，即 \([l,L-1]\) 对 \([1,R]\) 的贡献

根据上式，贡献为正

if(l>q[i].l) de[r].push_back((deal){q[i].l,l-1,i,1});
while(l>q[i].l) q[i].cnt-=pref[--l];

• \(L<l\)：也就是说 \(L\) 在 \(l\) 的左面，向右移动

每次减少的贡献是：

依然偷懒，右面化为 \(f(L,[1,L-1])\)

然后第一次离线计算右面的一堆

因为向右移动是删除，所以两个负号在一起抵消，不断进行加法操作

然后我们在 \(R\) 处保存信息，因为要减，贡献为负，设值 \(-1\)

if(l<q[i].l) de[r].push_back((deal){l,q[i].l-1,i,-1});
while(l<q[i].l) q[i].cnt+=pref[l++];

• \(R<r\)：上文已讨论过

if(r<q[i].r) de[l-1].push_back((deal){r+1,q[i].r,i,-1});
while(r<q[i].r) q[i].cnt+=pref[++r];

• \(R>r\)：\(R\) 在 \(r\) 的右面，向左移动

贡献是：

计算上式，然后保存信息即可

if(r>q[i].r) de[l-1].push_back((deal){q[i].r+1,r,i,1});
while(r>q[i].r) q[i].cnt-=pref[r--];

然后我们根据保存的信息进行第二次离线

这就完了么？

没有

上文说到我们偷懒省略了几步计算

但是这是OI不是MO，MO你证明少写几步兴许老师看不出来

于是我们要将没算的算上

首先有保存信息格式：de[a].push_back((deal){b,c,d,e})

其次一个位置对自己有贡献当且仅当 \(k=0\)

经过上文的讨论，我们发现只有左指针移动时会出现偷懒的情况（自己对自己做贡献的情况）

所以根据左指针保存信息的特点，对于一个位置 \(i\)，有且仅有 \([b,c]\) 中小于等于 \(i\) 的数会对自己作出贡献

因此判两个条件，然后进行二次离线即可

for(R int i=1,o,p;i<=n;i++){
	for(o=0;o<saf.size();o++) stk[d[i]^saf[o]]+=1;
	for(o=0;o<de[i].size();o++){
		for(p=de[i][o].l;p<=de[i][o].r;p++)
			q[de[i][o].pl].cnt+=de[i][o].op*(stk[d[p]]-(p<=i&&k==0))
}
for(R int i=1;i<=m;i++) q[i].cnt+=q[i-1].cnt,out[q[i].num]=q[i].cnt;
for(R int i=1;i<=m;i++) printf("%lld\n",out[i]);

次要内容

1. 我们肯定是要进行预处理的

for(R int i=1;i<=n;i++) d[i]=gi(),pl[i]=(i-1)/len+1;	//所属块的位置
for(R int i=1;i<16384;i++) popcnt[i]=popcnt[i>>1]+(i&1);
for(R int i=0;i<16384;i++) if(popcnt[i]==k) saf.push_back(i);
for(R int i=1;i<=m;i++){
	q[i].l=gi(),q[i].r=gi();
	q[i].num=i;
}
sort(q+1,q+m+1);
for(R int i=1;i<=n;i++){
	pref[i]=stk[d[i]];
	for(R int o=0;o<saf.size();o++) stk[d[i]^saf[o]]+=1;
}

2. 对于代码中莫队的转移（while部分）其实是可以直接前缀和计算的，之所以写成while是因为笔者认为4个while是莫队的灵魂（雾

莫队二次离线（第十四分块前体）

原文：https://www.cnblogs.com/zythonc/p/14722973.html