题解：P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了

yonghu10010 · 2025-04-23 15:48:32 · 题解

P12147 解题报告

（注：本题解思路与其他题解略有不同。）

某蒟蒻赛时被控 2h+……

一些思路

题目给出 n，k，让我们求出以下式子的值：

思路一：暴力

题目很简洁，暴力很好想。

既然这是个简简单单的表达式，自然可以直接使用 for 循环去求，每次以原表达式的形式加入 ans，最后直接输出即可。

思路二：找规律

本蒟蒻无法直接摁着二进制推式子得到较为简洁的表达式，只能打表观察。

打表看规律是一种思路，尤其是题目表达式比较抽象，即无法很形象地观察到本质的时候，打表将是一种好方法，值得一试。

细节构思

对于暴力没什么好说的，很简单。

对于每次查询直接循环计算即可。

时间复杂度 O(T \times n)，期望得分 20 分。

下面重点介绍思路二的延伸。

首先，看使用暴力程序打出的表：

这里展示了 k=0 的情况。如果你仍感觉云里雾里，看下面这个使用了数字大小作为高度的二维图像：

连了一些辅助线，是不是豁然开朗了呢？没错，它的形式像一棵二叉树！（注意是“像”，虽然有很多相似之处，但这里不能直接等同）

以下是关于该规律的简要证明（此时将数字默认转换为二进制）：

• 首先，每当加 2^{m-1} 次 1，数字的第 m 位就会 +1，这点易得；
• 其次，对于一个有从第 1 位开始长度为 x 的极长 1 串的数，由于该串会连续进位产生许多 0 和一个最高位的 1 以和原来的对应位置不相等，它的贡献为 2^{x+1}-1；
• 并且，对于每种贡献，每过 2^x 轮，这个数字从第 1 位开始就会出现一个长度至少为 x 的 1 串；
• 对于某数字，它从第 1 位开始的长度为 x 连续 1 串为极长 1 串的充要条件为该数的第 x+1 位是 0。
• 那么，由于每过 2^{((x+1)-1)+1} 轮，第 x+1 位就会进行两次 +1，即经过一次 0/1 循环，那个长度为 x 的连续 1 串就会成为一次极长 1 串。
• 结论：对于每种贡献每过 2^{x+1} 轮，就会出现一个数，它从第 1 位开始有一个长度为 x 的极长 1 串，贡献为 2^{x+1}-1。

于是，我们可以转化题意，将它转化为一种求树上区间和的问题。鉴于刚刚使用图像所得到的直观印象，我们也就能比较轻松地得到以下设计思路：

对于被查询一段区间，可以先计算它左一部分的和，再算右一部分的和，最后加上中间的和，即可得到结果。

可以使用分治算法实现。

自然而然地，我们可以想到一些优化：

1. 对于每一个节点的值，是可以预处理得到的。问题：如何计算？
2. 如果某段区间被全覆盖，可以直接返回它的区间和。问题：如何得到区间和？

观察图像可得，对于高度为 h 的一棵子树，它的根节点值为 2^h-1。这个可以现算，也可以预处理查询。（预处理时，每一步的值可以看作两倍上一步的值加上 1，后面就知道其意义了）
其次，对于一棵子树，它的各节点的值之和等于它的两棵子树和加上它自己的根节点值（刚刚已处理出）。

所以，这里只用一次简单的预处理，后面直接调用就行，时间复杂度 O(\log n)。
基本设计就已经结束了。

刚刚扯了这么一大堆，现在我们需要考虑到： k 怎么会一直安安稳稳地待在 0 值不动呢？ 所以，我们需要拓展刚刚的规律。

继续打表，比如 k=4 时，可以得到：16 个 16，16 个 48，16 个 16，16 个 112……

感觉有点似曾相识？把每个值除以 16（即 2^4，2^k），再将每 16 个相同的数只保留 1 个，我们就能发现这正是前文所提的 1，3，1，7……序列！至于为什么，也很简单：

• 因为加的是 2^k，那么对于二进制下的表示来说，低 k 位均不会受到任何改变；
• 那么按位异或的时候，也就会是全 0 了，得到的值也刚好就是 k=0 的基础上精确放大为原来的 2^k 倍；
• 至于每个数都出现 16 次，也是因为这一位本身大小就是 2^k，自然需要加 2^k 次 1 才能改变一次。

整理，得到以下结论：

对于所有的 k，它所形成的树的每个节点单值会成为原本的 2^k 倍，且范围也会变成原来的 2^k 倍，即每个节点形成了一个长度为 2^k 的块。

有了较为精确的表示方法，即可设计准确的代码表达。

首先，对于 k=0，以第 h 层节点为根节点的树覆盖范围长度为【左子树的覆盖范围】加上【节点本身的覆盖范围】和【右子树的覆盖范围】。其中第一项和第三项相等，第二项为 1，即可发现它在数值上刚好等价于预处理根节点值时得到的结果，可以直接拿来用。如果 k>0，直接左移 k 位即可。中间覆盖的长度刚好为 2^k。

那么，设该层树覆盖范围是 [l,r]，层序数为 h。

• 左子树覆盖的范围即为 [l,l+(b_{h-1} \times 2^k)-1]；
• 节点本身，即中间覆盖的范围为 [l+(b_{h-1} \times 2^k),l+(b_{h-1} \times 2^k)+2^k-1]；
• 最后右子树覆盖的范围是 [l+(b_{h-1} \times 2^k)+2^k,r]。

由于使用分治分为左右两半，于是最多约 \log{n} 层，且每层节点整体最多只访问 1 个，中间部分计算 O(1)；故总时间复杂度为 O(T \times \log{n})，足以通过此题。

思路整理完毕，细节见代码。

Coding Time

#include<cstdio>
long long T,n,k;
long long b[35];
long long b1[35];
int find(long long a){//返回最小能覆盖区间的树高度，这里使用二分查找（注意这里 res 的实际值为最大不能覆盖的高度，后面会 +1 调整）
    int l=1,r=31,mid,res=0;
    while(l<r){
        mid=(l+r)>>1;
        if(b[mid]>a){
            r=mid;
        }else{
            res=mid;
            l=mid+1;
        }
    }
    return res+1;
}
long long mn(long long a,long long b){//辅助函数
    if(a<b){
        return a;
    }
    return b;
}
long long mx(long long a,long long b){//辅助函数 +1
    if(a>b){
        return a;
    }
    return b;
}
long long query(int x,long long workl,long long workr,int bl,long long br){
    if(workl>br||workr<bl){//无交集区间，返回 0
        return 0;
    }
    if(workl>=bl&&workr<=br){
        return (b1[x]<<k)<<k;//直接返回：第一次还原长度，第二次还原值
    }
    long long res=0;
    res+=query(x-1,workl,workl+(b[x-1]<<k)-1,bl,br);//递归左子树
    res+=((mx(0,(mn(1<<k,(br-(workl+(b[x-1]<<k))+1))*b[x])))<<k);//计算中间区间。首先区间长度不能小于0，其次最大为2^k；否则就是查询区间的右端点减去中间区域的左端点。每个点的初值即为b[x]，左移k位放大即可
    res+=query(x-1,workl+(b[x-1]<<k)+(1<<k),workr,bl,br);//递归右子树
    return res;
}
void print(long long a){//朴实无华的快写
    if(a>9){
        print(a/10);
    }
    putchar(a%10+'0');
}
int main(){
    for(int i=1;i<=31;i++){//预处理：b为节点初值，b1为子树和
        b[i]=(b[i-1]<<1)|1;
        b1[i]=(b1[i-1]<<1)+b[i];
    }
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&k);
        if(n<(1<<k)){//如果n<2^k，所有的x的二进制第k位一定全0，即异或后会只剩下n个2^k，直接计算即可
            long long ans=(1<<k)*(n+1);
            print(ans);putchar('\n');
            continue;
        }
        long long n1=(n>>k);
        int mnum=find(n1)+1;//+1 进行调整
        print(query(mnum,0,(b[mnum]<<k)-1,0,n));putchar('\n');
    }
    return 0;//华丽结尾
}

-EOF-