Solution P11955 「ZHQOI R1」覆盖

· · 题解

这个题很人类智慧啊！

首先考虑 l=r=2^k 的情况。我们可以看成从 k-1 层的线段树添加 2^k 个叶子，然后让叶子尽可能被之前的区间进行拓展然后选到。

如上图。由于某个区间不能包含三个相邻的同层节点（否则就会合并成一个大的），因此 k-1 层的所有节点最优情况下都可以连向一条到第 k 层的边，即最优情况下有 2^{k-1} 个点已经被连好了。

考虑上图的这种构造方式，首先每个 k-1 层的节点都对应一个 k 层的节点，且剩下的节点除了头尾之外两两配对，配对的两个可以只使用一次区间覆盖。于是发现这是一种较为优秀的构造方式。

设 f(k) 表示长度为 2^k 时的答案（这里并没有考虑 [1,2^k] 的区间，因此答案还要加 1），则有 f(k)=f(k-1)+2^{k-2}+1，边界为 f(0)=0,f(1)=2。容易做到 O(\log V+q)。

解决了特殊性质 AB 后，考虑拓展这个做法。例如从 2^{k-1} 个点到 2^k 个点，过程中每次都相当于添加了一个叶子。如果叶子位置是那些已经被覆盖的点就不用管，否则如果在上图黄色的区间内，则需要额外操作。发现加入的前 2^{k-2} 个叶子都需要额外的一次操作覆盖，而后面的叶子无需操作，因此区间 [2^{k-1},2^k)（记为 [l,r]）的答案即为 f(k-1)(r-l+1)+\sum_{i=1}^{2^{k-2}}(r-l-i+1)，等差数列求和即可。

这是完全包含的情况，不完全包含的情况（即要求 x 的前缀答案和，x 夹在 l,r 中间）同理。答案变成 f(k-1)(x-l+1)+\sum_{i=1}^{2^{k-2}}\max(x-l-i+1,0)。也可以快速求出。

场上写的 O(q\log V) 可过。精细实现即可做到 O(\log V+q)。

const int P=353442899;
int pw[80];

il int count(int x){
    if(!x)return 0;
    int ans=x;
    forto(i,1,61){
        int l=1ll<<i,r=(1ll<<(i+1))-1;if(l>x)break;
        if(r<=x){
            if(i>1){
                ans+=(__int128)pw[i]%P*(r-l+1)%P,ans%=P;
                int d=1ll<<(i-1);
                ans+=(__int128)(r-l+r-l-d+1)*d/2%P,ans%=P;
            }else if(i==1)ans+=5;
        }else{
            if(i>1){
                // cerr<<l<<' '<<x<<' '<<pw[i]<<'\n';
                ans+=(__int128)pw[i]%P*(x-l+1)%P,ans%=P;
                int d=min(1ll<<(i-1),x-l);//cerr<<d<<'\n';
                ans+=(__int128)(x-l+x-l-d+1)*d/2%P,ans%=P;
            }else if(i==1)ans+=2;
        }
    }
    return ans;
}

il void work(){
    int l=read(),r=read();
    printf("%lld\n",(count(r)-count(l-1)+P)%P);
}

signed main(){
    pw[0]=0,pw[1]=2;
    forto(i,2,60)pw[i]=(pw[i-1]+(1ll<<(i-2))+1)%P;
    // forto(i,1,60)cerr<<pw[i]<<'\n';
    int t=read();while(t--)work();
    return 0;
}