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)

。

CPP

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;
}

Solution P11955 「ZHQOI R1」覆盖

文章操作

相关推荐

评论

Solution P11955 「ZHQOI R1」覆盖