点分治复杂度问题+WA求助

__gcd @ 2020-04-02 20:03:36

by __gcd @ 2020-04-02 20:31:05

假如对比一下

P4178

int calc(int u, int dist)
{
    summar = 0;
    memset(dis, 0, sizeof(dis));
    getdis(u, 0, dist);
    sort(dis + 1, dis + 1 + summar);
    int lef = 1, rig = summar, res = 0;
    while(lef <= rig)
    {
        if(dis[lef] + dis[rig] <= k){res += rig - lef; lef++;}
        else rig--;
    }
    return res;
}

听说这个的总复杂度是 O(n^2\log n)

那么本题

void calc(int u, int dist, int w)
{
    summar = 0;
    memset(dis, 0, sizeof(dis));
    getdis(u, 0, dist);
    for(int i = 1; i <= summar; i++)
    {
        for(int j = i + 1; j <= summar; j++)
        {
            app[dis[i] + dis[j]] += w;
        }
    }
    return ;
}

这个是多少

by chenxinyang2006 @ 2020-04-02 20:31:46

@一只大头 哦，我懂你在说什么了，总复杂度确实是每个点度数平方的和

by chenxinyang2006 @ 2020-04-02 20:32:46

P4178 那个不是 O(n \log n \log n) 吗？

你下面那个复杂度不对吧

by chenxinyang2006 @ 2020-04-02 20:33:02

菊花图会死

by chenxinyang2006 @ 2020-04-02 20:33:15

下面那个实际上是 O(n \log n + n ^ 2)

by __gcd @ 2020-04-02 20:34:50

@chenxinyang2006 那个复杂度写错了QAQ

by chenxinyang2006 @ 2020-04-02 20:36:41

一般复杂度不对的都会死在菊花图，你看看菊花图是不是特别慢就知道复杂度对不对了

by __gcd @ 2020-04-02 20:36:50

@chenxinyang2006 我很想知道下面的那个是怎么算出来的

by __gcd @ 2020-04-02 20:37:25

我们老师就是不讲复杂度QAQ

by chenxinyang2006 @ 2020-04-02 20:41:51

@一只大头 正常写法（上面那个复杂度）：

至多只有 \log n 层分治，每层求离重心距离只会访问每个点一次，O(n)

计算答案的时候使用双指针，复杂度是 度数 的，每层的度数总和是 O(n) 级别

所以总复杂度 n \log n（这份代码需要乘上排序的 \log n）

奇怪的写法（下面的）：

求离重心距离的复杂度也是 n \log n 的，但是枚举两个子树的复杂度是 重心度数 ^ 2 的，菊花图就死了