题解：P11955 「ZHQOI R1」覆盖

· · 题解

更好的阅读体验

非常趣味的一道脑子防锈题。

考虑分治，对于一棵线段树，我们先把左右两个子树的答案计算出来，再考虑中间有哪些可以合并的部分。下文所说的“询问”就是题目中的“区间定位”。

如果我们在同一棵子树（即左子树或右子树）合并两次相邻的询问，那么一定会将询问的节点向着根节点移动一步，这是不好的，因为还要多一次询问才能把这个节点的空补上。

所以我们只能指望通过合并两棵子树内的节点达到最小化答案的目的。由于同一棵子树内的点不能合并，我们只能合并左子树极右链和右子树极左链的点。能省去的长度就是两条链长度的较小者。设 f_n 为 n 个叶子的线段树的答案，L,R 分别为左右子树叶子节点数目，则有

f_n = f_L + f_R - \min(\lfloor \log_2L\rfloor + 1, \lceil\log_2R\rceil + 1) + 1

至此，我们可以做到 O(r + T) 解决问题。但还不是很牛。

打个表，我们会发现这个序列非常特殊。

1 3 4 5 6 7 7 8 9 10 11 12 12 12 12 13 14 15 16 17 18 19 20 21
21 21 21 21 21 21 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
36 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 40 41
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71 71 71 71 71 ...

它是由若干个公差为 1 的等差数列，和若干段相同的值拼起来的。再看看相同值的区间与值有什么特点，

l r: value
6 7: 7
12 15: 12
24 31: 21
48 63: 38
96 127: 71
192 255: 136
384 511: 265
768 1023: 522
1536 2047: 1035
3072 4095: 2060
6144 8191: 4109
12288 16383: 8206
24576 32767: 16399
49152 65535: 32784
98304 131071: 65553
196608 262143: 131090
393216 524287: 262163
...

每一段的左端点都是 6 乘上 2 的幂，右端点都是 2 的幂 -1，并且值是形如 2^x + x + 1 的形式。那么关于端点的性质告诉我们在一定范围内只有 \log 段连续的数字，这是很好的。那么我们把这些段拎出来，随后把查询区间和转换成前缀和相减，那么就做完了。复杂度 O(T \log r)，注意乘法和取模的顺序。

#include<bits/stdc++.h>
#define int __int128
#define endl '\n'
using namespace std;
const int MOD=353442899,inv2=MOD+1>>1;
struct Node{int l,r,val;};
int T,n,f[1000006],tot;Node b[70];
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
    return ret*f;
}
inline void write(int k)
{
    if(k<0)putchar('-'),k=-k;
    int nnum[20],ttp=0;
    while(k)nnum[++ttp]=k%10,k/=10;
    if(!ttp)nnum[++ttp]=0;
    while(ttp)putchar(nnum[ttp--]^48);
}
int getsum(int l,int r){return (l+r)*inv2%MOD*(r-l+1)%MOD;}
int query(int x)
{
    if(!x)return 0;
    int sum=-1;
    for(int i=1;i<=tot;i++)
    {
        int l=(i==1?1ll:b[i-1].r+1),r=min(b[i].l-1,x),val=(i==1?2ll:b[i-1].val+1)%MOD;
        sum+=getsum(val,val+r-l),sum%=MOD;
        if(r==x)break;
        l=b[i].l,r=min(b[i].r,x),val=b[i].val;
        sum+=val*(r-l+1+MOD)%MOD,sum%=MOD;
        if(r==x)break;
    }
    return sum;
}
main()
{
    T=read();
    for(int l=6,r=7;l<=1e18;l<<=1,r=r<<1|1)
        b[tot+1]={l,r,((1ll<<tot+2)+tot+3)%MOD},tot++;
    while(T--)
    {
        int l=read(),r=read();
        write(((query(r)-query(l-1))%MOD+MOD)%MOD),putchar('\n');
    }
}