[洛谷P4887]第十四分块(前体)

题目大意：

给定一个长度为\(n\)的序列\(a\)，\(k\)，和\(m\)次询问。

每次询问给定区间\([l,r]\)，求满足\(l\leqslant i< j\leqslant r\)且\(\_\_ \text{builtin}\_ \text{popcount} (a_i\oplus a_j)=k\)的数对\((i,j)\)的个数。

40MB。

解题思路：

二次离线莫队lxl黑科技。

对于一次询问\([l,r]\)，我们考虑右端点往右移动一格后变成\([l,r+1]\)，多出来的数其实是\(a_{r+1}\)在\([l,r]\)内的贡献。

而这个贡献相当于\(a_{r+1}\)在\([1,r]\)内的贡献减去\(a_{r+1}\)在\([1,l-1]\)内的贡献。

而\(a_{i+1}\)在区间\([1,i]\)内的贡献可以前缀和预处理出来，这部分贡献可以\(O(1)\)计算。

而当右指针移动的时候，左指针不会动，所以\([1,l-1]\)这个区间是不会变的。

设指针\(r\)往右移动到\(r'\)，则把\([r+1,r']\)塞进\(v_{l-1}\)里去，表示\([1,l-1]\)这段区间对\([r+1,r']\)有贡献。往左移动同理，记录一下贡献的正负即可。

左指针移动的话，则反着再记录一个即可。注意右指针移动的时候，左指针没有动过，而左指针移动的时候，右指针已经移动完了。

而莫队保证每个指针移动的总距离是\(O(n\sqrt n)\)的，也就是说一个vector里存的区间总长是\(O(n\sqrt n)\)的，那么拿出来暴力计算即可。

要用一个桶记录当前状态，可以做到\(O(\binom{14}{k})\)插入（插入一个数，把这个数异或所有合法数的桶都+1），\(O(1)\)查询。

注意最后得到的结果是与上一次的贡献差，最后要做一个前缀和。

时间复杂度\(O(n\binom{14}{k}+n\sqrt n)\)，常数巨大。空间复杂度\(O(n+m)\)。

C++ Code：

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

#include<cstring>

#define lim 16384

#define N 100005

#define reg register

class istream{

    char buf[15000003],*s;

    public:

        inline istream(){

            buf[fread(s=buf,1,15000001,stdin)]='\n';

        }

        template<typename T>

        inline istream&operator>>(T&rhs){

            for(rhs=0;!isdigit(*s);++s);

            while(isdigit(*s))rhs=rhs*10+(*s++&15);

            return*this;

        }

}cin;

struct ostream{

    char buf[8000005],*s;

    inline ostream(){s=buf;}

    inline void operator<<(long long d){

        if(!d){

            *s++='0';

        }else{

            static long long w;

            for(w=1;w<=d;w*=10);

            for(;w/=10;d%=w)*s++=d/w^'0';

        }

        *s++='\n';

    }

    inline ostream&operator<<(const char&c){*s++=c;return*this;}

    inline~ostream(){fwrite(buf,1,s-buf,stdout);}

}cout;

int n,m,k,buc[lim+1],a[N],K[4000],KS;

long long ans[N],out[N],L_R[N],R_L[N];

struct que{

    int l,r,id;

    inline bool operator<(const que&rhs)const{

        return((l/333!=rhs.l/333)?(l<rhs.l):(r<rhs.r));

    }

}q[N];

struct node{

    int l,r,id,op;

};

std::vector<node>L[N],R[N];

int main(){

    cin>>n>>m>>k;

    if(k>14){for(int i=1;i<=m;++i)puts("0");return 0;}

    for(int i=0;i<lim;++i)

    if(__builtin_popcount(i)==k)K[KS++]=i;

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

        cin>>a[i];

        L_R[i]=buc[a[i]]+L_R[i-1];

        reg int j=0;

        for(;j+8<KS;j+=8)

        ++buc[a[i]^K[j]],++buc[a[i]^K[j+1]],++buc[a[i]^K[j+2]],++buc[a[i]^K[j+3]],

        ++buc[a[i]^K[j+4]],++buc[a[i]^K[j+5]],++buc[a[i]^K[j+6]],++buc[a[i]^K[j+7]];

        for(;j<KS;++j)++buc[a[i]^K[j]];

    }

    memset(buc,0,sizeof buc);

    for(int i=n;i;--i){

        R_L[i]=buc[a[i]]+R_L[i+1];

        reg int j=0;

        for(;j+8<KS;j+=8)

        ++buc[a[i]^K[j]],++buc[a[i]^K[j+1]],++buc[a[i]^K[j+2]],++buc[a[i]^K[j+3]],

        ++buc[a[i]^K[j+4]],++buc[a[i]^K[j+5]],++buc[a[i]^K[j+6]],++buc[a[i]^K[j+7]];

        for(;j<KS;++j)++buc[a[i]^K[j]];

    }

    for(int i=1;i<=m;++i)cin>>q[i].l>>q[q[i].id=i].r;

    std::sort(q+1,q+m+1);

    q[0].l=1,q[0].r=0;

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

        const que&now=q[i],pre=q[i-1];

        ans[i]+=L_R[now.r]-L_R[pre.r]+R_L[now.l]-R_L[pre.l];

        if(now.r>pre.r)

        R[pre.l-1].push_back((node){pre.r+1,now.r,i,-1});else

        if(now.r<pre.r)

        R[pre.l-1].push_back((node){now.r+1,pre.r,i,1});

        if(now.l<pre.l)

        L[now.r+1].push_back((node){now.l,pre.l-1,i,-1});else

        if(now.l>pre.l)

        L[now.r+1].push_back((node){pre.l,now.l-1,i,1});

    }

    memset(buc,0,sizeof buc);

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

        reg int j=0;

        for(;j+8<KS;j+=8)

        ++buc[a[i]^K[j]],++buc[a[i]^K[j+1]],++buc[a[i]^K[j+2]],++buc[a[i]^K[j+3]],

        ++buc[a[i]^K[j+4]],++buc[a[i]^K[j+5]],++buc[a[i]^K[j+6]],++buc[a[i]^K[j+7]];

        for(;j<KS;++j)++buc[a[i]^K[j]];

        for(node j:R[i]){

            const int l=j.l,r=j.r;

            reg long long t=0,k=l;

            for(;k+8<=r;k+=8)

            t+=buc[a[k]],t+=buc[a[k+1]],t+=buc[a[k+2]],t+=buc[a[k+3]],

            t+=buc[a[k+4]],t+=buc[a[k+5]],t+=buc[a[k+6]],t+=buc[a[k+7]];

            for(;k<=r;++k)t+=buc[a[k]];

            ans[j.id]+=t*j.op;

        }

    }

    memset(buc,0,sizeof buc);

    for(int i=n;i;--i){

        reg int j=0;

        for(;j+8<KS;j+=8)

        ++buc[a[i]^K[j]],++buc[a[i]^K[j+1]],++buc[a[i]^K[j+2]],++buc[a[i]^K[j+3]],

        ++buc[a[i]^K[j+4]],++buc[a[i]^K[j+5]],++buc[a[i]^K[j+6]],++buc[a[i]^K[j+7]];

        for(;j<KS;++j)++buc[a[i]^K[j]];

        for(node j:L[i]){

            const int l=j.l,r=j.r;

            reg long long t=0,k=l;

            for(;k+8<=r;k+=8)

            t+=buc[a[k]],t+=buc[a[k+1]],t+=buc[a[k+2]],t+=buc[a[k+3]],

            t+=buc[a[k+4]],t+=buc[a[k+5]],t+=buc[a[k+6]],t+=buc[a[k+7]];

            for(;k<=r;++k)t+=buc[a[k]];

            ans[j.id]+=t*j.op;

        }

    }

    for(int i=1;i<=m;++i)ans[i]+=ans[i-1],out[q[i].id]=ans[i];

    for(int i=1;i<=m;++i)cout<<out[i];

    return 0;

}

巴特西

[洛谷P4887]第十四分块(前体)

最新文章

热门文章