题解 P7143 【[THUPC2021 初赛]线段树】

xh39 · 2021-01-03 23:26:50 · 题解

注:正解为暴力的优化,请先看暴力。

本篇题解中的时间复杂度均为一组数据中的时间复杂度,所以最终复杂度还要乘数据组数t。

?

小 L 想请你帮他计算出cover(A,B)的期望值与\frac{n(n+1)}{2} 的乘积对 1, 000, 000, 007 取模的结果，可以发现此结果一定是一个整数。

为什么是整数?遇到乘...一定是整数先思考为什么,大部分时候都有利于做题。

任意选两种情况总共有C_{n}^{2}=\frac{n(n+1)}{2}种方案,所以题目就是要求sum\{cover(i,j)\}(0<i<=j<=n),即所有cover的和。

暴力O(n)

貌似直接算答案时间复杂度为O(n^2\times log_2(n)),所以肯定不行。

于是想到了算贡献.可是怎么算贡献呢?

设f[n]为长度为n的线段树的贡献。left为左子树,right右子树。

我们可以来模拟一下转移的过程,转移的过程是一种类似点分治而非点分治的过程。

        1,7
       /   \
     1,4    5,7
    / \     /  \
 1,2 3,4  5,6  7
 /\  /\   /\
1 2 3 4  5 6
(节点数为7的线段树)

首先,按照点分治的思路,先算子树内的贡献:f[left]+f[right]

然后算跨两子树间的贡献:[1,7]这个区间需从[1,4]选出一部分,[5,7]选出一部分,由于两个部分互不干扰,所以可以相加。

注:+left的原因是每个右子树的前缀区间都需要左儿子来覆盖,即加left个1。

-1的原因是覆盖整个区间时会用左儿子和右儿子2个结点覆盖,事实上直接选用根节点就可以了。

同理,就不列fr了,具体见代码。

得出f[n]=(f[left]+f[right])+(fr[left]\times size[right]+fl[right]\times size[left])//注:这里加分间打括号的原因是区分子树内和跨两子树。

关于如何求left和right,就看你的线段树基础了。size[left]=(size[root])/2向上取整,size[right]=size[root]/2向下取整,至于怎么证,我也不知道。

暴力代码(由于反正会tle,就没开long long和取模了):

#include<iostream>
using namespace std;
int fl(int n){
    if(n==1){ //边界条件。当只有1个结点时3个状态都为1。
        return 1;
    }
    int left,right=n>>1;
    left=n-right; //向上取整=n-向下取整。
    return fl(left)+fl(right)+right-1;
}
int fr(int n){
    if(n==1){
        return 1;
    }
    int left,right=n>>1;
    left=n-right;
    return fr(left)+left+fr(right)-1;
}
int fm(int n){
    if(n==1){
        return 1;
    }
    int left,right=n>>1;
    left=n-right;
    return fm(left)+fm(right)+fr(left)*(right)+fl(right)*(left)-1;
}
int main(){
    int t,n,i;
    cin>>t;
    for(i=0;i<t;i++){
        scanf("%d",&n);
        cout<<fm(n)<<"  "<<fl(n)<<" "<<fr(n)<<endl;
    }
}

正解O(log_{2}(n))

发现递归查询了很多相同的状态,很容易想到记忆化。但是有n<=10^{18},那么多状态数组存不下。这里有3种办法。

1.哈希。(状态较多时容易被卡,不推荐,除非是在没别的办法)

2.map。(时间复杂度变为O(log_2(n)^{2}),可能tle。(注意本题多组数据,需要乘t=1000,而map常数较大,递归常数也大,不冒这个风险,除非实在没别的办法)

3.本题解的方法,后面介绍。

观察我们需要用到哪些状态。

为方便,(n+a)/b表示为n+a/b,即先算加法。上节点为左子树。

再画多一点节点(由于latex的一些性质,这里只画了3层),就会发现,第i层的节点只会是n+a/(2^{i})(a为0至2^i的全排列)

为什么a为全排列呢?可以用二进制解释。

一个第i层节点数为n+a/b的结点,左结点一定是n+(a+2^i)/b。右节点也为n+a/b。那么左节点即为二进制第i位为1。否则为0。

那么左右子树的二进制序列就变成了全排列。

那知道了a为n+a/(2^i)全排列。那么就可以得出一个性质:第i层子树大小要么为(n/2^i),要么为(n/2^i+1)。

然后就得出了一个性质:同一层只有2种节点,且相差为1,这让我们想到了奇偶性讨论。那我们可以这样设状态。