题解 P6562 【[SBCOI2020] 归家之路】

JohnVictor · 2020-05-21 21:03:47 · 题解

放上官方题解。

令序列长 m=2^n。

首先对于前 5\% 的数据可以直接暴力。复杂度 O(mq)。

暴力枚举子集的方法是（这里是 c++ 代码）

int f=x^y;
for(int t=x^y;t>=0;t=(t-1)&f)

当然还有什么都不发生的情况，也就是不存在满足要求的 c。这个可以使用 a and b=a 进行特判。

继续开始思考后面的部分分。之后都假设所有的修改和询问都是有效的，也就是 a and b=a一直成立。

这个修改、询问的形式类似一个区间，那么需要知道一个前置知识 高维前缀和。如果不知道的话可以学一下，比较简单。

那么类比不带修直接求区间的和，我们考虑用几个高维前缀和相加减去表示一个询问的答案。

这里可以从简单的情况开始考虑。如果 a=0，那么就直接是一个高维前缀和的答案；那么继续考虑，令 sum(i) 为 i 的高维前缀和，如果 a=1，那么询问 (a,b) 的答案是一些 a_c 的和，其中 c 是奇数并且 c and b=b。那么这个答案比 sum(b) 小了 c 是偶数，并且 c and b=b 的位数之和。后面的那个恰好可以用 sum(b-1) 表示。

思路逐渐明朗起来，如果 x 是 b 与 a 相同且二进制位 1 的一位的值，那么我们可以得到

query(a,b)=query(a-x,b)-query(a-x,b-x)

这个式子可以位运算进行优化，x=a&-a，a-x 可以用 a^x 表示。

这个看似还没啥用——如果 a,b 相同那么这个复杂度还是 m 级别的。但是仔细分析：

如果 a,b 二进制不同的位有 x 位，相同的有 y 位，其中 x+y=n，那么直接暴力计算就可以用 O(2^x) 次计算完成；如果用上面那种方法，它的复杂度是 O(2^y)。

进行特判并且选择可以做到 O(2^{\min(x,y)})，也就是单次询问 O(\sqrt m)。这个算法可以通过第二档部分分。

这里有一个很小的优化，没什么用：

可以快速预处理出 0 到(2^n-1) 中每一个数有多少个二进制 1，这样查询二进制 1 的个数就从 O(\log m) 变成了 O(1)。具体实现和 FFT 中的那个 rev 数组类似：

for(int i=0;i<(1<<n);i++)count[i]=count[i>>1]+(i&1),rev[i]=(1<<n)-i-1;

其实这么进行修改也是 O(\sqrt m) 的，但是唯一的问题就是无法及时更新。如果询问都在修改后面，可以考虑懒标记，用数组 curr 记录。如果 curr[i] 记录了值，那么就代表所有 i 的子集都要加上这个值。

这里用代码更清楚一点：

void modify(int x,int y,uint z)
{
    if(count[x^y]<=n/2)
    {
        int f=x^y;
        for(int t=x^y;;t=(t-1)&f){
            a[t|x]+=z;
            if(t==0)
                break;
          //这一部分是对修改值不多的情况进行暴力
        }
        return;
    }
    if(x==0)
    {
        curr[y]+=z;//如果x=0那么就可以直接打上懒标记
        return;
    }
    int lbt=x&-x;
    modify(x^lbt,y,z);
    modify(x^lbt,y^lbt,-z);//与 query 部分类似的递归
}

等到所有修改结束后可以下放懒标记，暴力下放的复杂度是 O(3^n)，总时间复杂度 O(\sqrt mq+3^n)，可以通过第三档部分分。

然而这里并不是没有优化的空间了。下放懒标记的过程完全可以看成又一次高维前缀和。

本来的高维前缀和上的值是它的所有子集的和；而这时候需要加的值，是所有以它为自己的懒标记的和。

举个栗子，如果一个数的二进制表示是 001，那么高维前缀和中就是 000,001 的和，在这种情况下要加上 001,011,101,111 这四个懒标记的和。所以这样只用反着来一遍高维前缀和就行了。

为了加速，我预处理了 rev 数组代表一个数二进制取反后的结果，因为这里不能直接用 ~。（这个 rev 不是 FFT 中的 rev）

话不多说上代码：

void update()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
        {
            if(j&(1<<i))
                curr[rev[j]]+=curr[rev[j^(1<<i)]];
        }
  //这里是反着的高维前缀和
    for(int i=0;i<(1<<n);i++)
        a[i]+=curr[i];
    for(int i=0;i<(1<<n);i++)
        pres[i]=a[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
            if(j&(1<<i))
                pres[j]+=pres[j^(1<<i)];
}

其中 pres 是高维前缀和数组。这一次 update 的复杂度是高维前缀和的复杂度 O(n2^n)。

好了，各位大佬们看到这里，正解已经呼之欲出了：分块！

我们假设块长为 s，一共 t 块。

修改还是正常修改，查询还是正常查询。这里复杂度是 O(q \sqrt m)。

查询的时候，唯一的问题就是计算块内贡献。这个可以位运算 O(1) 计算每个贡献，复杂度是 ms；每一块的 update 的复杂度是 O(tn2^n)，那么我们可以得到总的复杂度可以达到 O(m \sqrt {nq}+q \sqrt m)，在块长为 \sqrt{nq} 时最优。

块内的贡献还是有细节的。大概是这两种情况：

（1）一个修改的数和询问的数没有相同的。

（2）有一部分相同。

这个位运算有很多种实现方法，直接上代码：

for(int i=1;i<=cnt;i++)
            {
                num=(s[i].a|a)&(s[i].b&b);
                if(num==int(s[i].a|a))
                {
                    num=(s[i].a|a)^(s[i].b&b);
                    ans+=(1<<count[num])*s[i].k;
                }
            }
            cout<<ans<<endl;

std 的长度 2235byte，作为数据结构还是比较良心的。