题解 P4887 【第十四分块(前体)】

· · 题解

其实是lxl题里良心的题了……毕竟就几十行(当然细节比较恶心就是了)

更加良心的是这!题!不!卡!常!

管他什么题总之lxl数据结构天下第一

本题题解:莫队+扫描线(二次离线莫队)

首先这是一道无修改的区间数点对问题

那么解决这类问题我们可以使用莫队算法来在O(N\sqrt{m})的时间内处理这些东西

但是前提是我们需要在O(1)(有些时候O(logn)可以忍受)实现三个操作

1.已知(l,r)递推到(l,r+1)

2.已知(l,r)递推到(l+1,r)

3.已知(l,r)递推到(l-1,r)

(之所以没有右端点右移的操作是因为我们可以直接规避掉这个没卵用的操作(当然你奇偶性排序莫队卡常数这个写法当我没说,不过对应到这道题上就是你多讨论一种情况))

那么对于这道题来讲我们似乎直接插入是O(C(k,14))的这个复杂度绝对无法接受的

但是我们看一下我们是如何插入一个值的呢？假设我们让右端点+1的话,我们实际上是求(l,r)这段区间里有多少个数和a_{r+1}异或起来恰好有k个1

那么这个问题其实是可以转化为求出(1,l-1)这段区间里有多少个数和a_{r+1}异或起来恰好有k个1,求出(1,r)这段区间里有多少个数和a_{r+1}异或起来恰好有k个1,然后二者相减一下就可以了

那么我们发现这是一堆针对于前缀的询问了此时我们可以将这些询问全部离线下来然后跑一边扫描线似乎就可以求出答案了？

然后你发现你这样写甚至连样例都过不去

为什么呢？

因为我们在写莫队的时候会发现一个重要的事实就是我们插入一个点和删除一个点的时候本质上是在求答案的变化量也就是这个答案和上一个问题的答案差了多少

因此如果我们刚才离线之后跑扫描线我们只能知道每个答案和上一个问题的答案差了多少

所以我们最后需要做一次前缀和将问题的答案还原

好了那么我们现在已经有了一个比较trival的算法了很遗憾的是这个算法需要O(N\sqrt{M})的空间复杂度并且常数相当的大……

那么我们考虑卡卡空间并且卡卡常数

让我们来煮个栗子

假设我们现在需要从区间(233,666)转移到区间(262,700)

那么首先我们先让右端点不停的+1直到这个右端点变成了700为止

那么我们的询问就会被拆成这样的一堆询问

询问 (1,666)这个区间中有几个数字和a_{667}异或起来有k个1

询问 (1,667)这个区间中有几个数字和a_{668}异或起来有k个1

询问 (1,668)这个区间中有几个数字和a_{669}异或起来有k个1

......

询问 (1,669)这个区间中有几个数字和a_{700}异或起来有k个1

以上的询问全部是需要加上的值(权值为+1)

还有需要减去的值

询问 (1,232)这个区间中有几个数字和a_{667}异或起来有k个1

询问 (1,232)这个区间中有几个数字和a_{668}异或起来有k个1

询问 (1,232)这个区间中有几个数字和a_{669}异或起来有k个1

......

询问 (1,232)这个区间中有几个数字和a_{700}异或起来有k个1

这些询问的权值全部是-1

Case1:求+1部分的和

那么我们可以跑一边扫描线，对于每一个位置i求出(1,i-1)这个前缀有多少个数字和a_{i}异或起来有k个1

具体点来讲我们实现一个O(C(7,14))插入O(1)询问的数组res

假设我们跑扫描线的时候跑到了第i个点那么res(j)就表示(1,i)这个区间中有多少个数字和a_{j}异或起来有k个1

那么我们插入一个a值的时候就直接大力的枚举所有有k个1的数字val然后令res(a \oplus val)++就行了

接下来我们维护一个变量K表示“对于(1~i)中的每一个位置i,满足(1,i-1)这个前缀a_{i}异或起来有k个1的数字的数目的和”

那么以刚才的例子为例,我们只需要用扫到700这个位置的K减去扫到666这个位置的K就行了

Case2:求-1部分的和

我们发现这个部分是对着(1,232)这个前缀询问了(667,700)这个区间里有多少个数字异或起来有k个1

那么我们可以在232这个位置开一个vector然后push一个区间(667,700) 就可以了,我们扫描线跑到232这个位置的时候就暴力询问一遍(667,700)这个区间里的所有值挨个询问一下就可以了

然后我们发现我们就如此这般的将询问的空间复杂度压到了O(m)的级别

接下来我我们唯一需要做的事情就是正着跑一遍扫描线处理所有的右端点变动情况接下来跑一遍扫描线处理所有左端点的变动情况了

复杂度O(C(k,17)n+n\sqrt{m})

上代码~


#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;const int N=1e5+10;const int M=16384+10;typedef long long ll;
int res[M];int siz[M];int val[M];int tp;ll ans[N];int a[N];int n;int m;int k;int B;
struct nod{int p;int tim;};vector <nod> mrk1[N],mrk2[N];
struct data{int l;int r;int tim;};vector <data> sp[N],spa[N],spm[N];
struct qry{int l;int r;int tim;}qr[N];ll trs;
inline bool cmp1(const qry& a,const qry& b){return a.l<b.l;}
inline bool cmp2(const qry& a,const qry& b){return (a.r==b.r)?a.l<b.l:a.r<b.r;}
inline void subsolve(int dl,int dr)//二次离线 
{
    if(dl==dr)return;sort(qr+dl,qr+dr,cmp2);
    int l=qr[dl].l;int r=qr[dl].r;int t=qr[dl].tim;int nl=l;int nr=r;
    mrk1[l-1].push_back((nod){-1,t});mrk1[r].push_back((nod){1,t});sp[l-1].push_back((data){l,r,t});
    for(int i=dl+1;i!=dr;i++)
    {
        l=qr[i].l;r=qr[i].r;t=qr[i].tim;
        if(nr!=r)
        {
            mrk1[nr].push_back((nod){-1,t}),mrk1[r].push_back((nod){1,t});
            sp[nl-1].push_back((data){nr+1,r,t});
        }
        if(nl!=l){mrk2[nl].push_back((nod){-1,t}),mrk2[l].push_back((nod){1,t});}
        if(nl<l){spa[r+1].push_back((data){nl,l-1,t});}
        if(l<nl){spm[r+1].push_back((data){l,nl-1,t});}nl=l;nr=r;
    }
}
inline void subsolve2(int dl,int dr)//前缀和 
{for(int i=dl+1;i<dr;i++)ans[qr[i].tim]+=ans[qr[i-1].tim];}
inline void ins(int a){for(int i=1;i<=tp;i++)res[val[i]^a]++;}//插入 
int main()
{
    for(int i=1;i<16384;i++)siz[i]=siz[i>>1]+(i&1);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=0;i<16384;i++)if(siz[i]==k)val[++tp]=i;
    for(int i=1;i<=m;i++)scanf("%d%d",&qr[i].l,&qr[i].r),qr[i].tim=i;
    sort(qr+1,qr+m+1,cmp1);B=n/sqrt(m)+1;
    for(int i=B,dl=1,dr=1;;i=min(i+B,n),dl=dr)
        {while(qr[dr].l<=i&&dr<=m)dr++;subsolve(dl,dr);if(i==n)break;}
    for(int i=1;i<=n;i++)//正着扫描线一遍 
    {
        trs+=res[a[i]];ins(a[i]);
        vector <nod> :: iterator it;vector <data> :: iterator it1;
        for(it=mrk1[i].begin();it!=mrk1[i].end();++it){ans[it->tim]+=trs*it->p;}
        for(it1=sp[i].begin();it1!=sp[i].end();++it1)
            for(int j=it1->l;j<=it1->r;j++){ans[it1->tim]-=res[a[j]];}
    }for(int i=0;i<16384;i++)res[i]=0;trs=0;
    for(int i=n;i>=1;i--)//倒着扫描线一遍 
    {
        trs+=res[a[i]];ins(a[i]);
        vector <nod> :: iterator it;vector <data> :: iterator it1;
        for(it=mrk2[i].begin();it!=mrk2[i].end();++it){ans[it->tim]+=trs*it->p;}
        for(it1=spa[i].begin();it1!=spa[i].end();++it1)
            for(int j=it1->l;j<=it1->r;j++)ans[it1->tim]+=res[a[j]];
        for(it1=spm[i].begin();it1!=spm[i].end();++it1)
            for(int j=it1->l;j<=it1->r;j++)ans[it1->tim]-=res[a[j]];
    }
    for(int i=B,dl=1,dr=1;;i=min(i+B,n),dl=dr)
        {while(qr[dr].l<=i&&dr<=m)dr++;subsolve2(dl,dr);if(i==n)break;}
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;//拜拜程序~ 
}