noip2016day1t2天天爱跑步 树链剖分 线段树 or lca 桶

先讲一下我最初的暴力的做法吧

25分暴力

这个随便做吧,随便dfs一下就有20分了

40分暴力

先讲我当时naive的做法吧

由于是对一条链的操作,对于向下的链我把它拆成从1号点到t的和1s-1的,然后分别对于每一条链,用线段树对链上的点进行更新就行了

60分:

我们可以观察到,对于一个点有贡献的话,那么就是这个点到1号点的深度等于这个点的watch[i],于是我们用树剖维护对于每一条路径染色,最后对于每一个点算一下染色到了多少次就行了。

80分并不会做

后来仔细的看了一下题解发现40分的做法并不是我这么做

你要逆向思维,对于一个点,如果他被统计到了答案,只有两种情况是向上走的或者向下走的

于是起点只有两种深度deep[i]-watch[i]或者 deep[i]+watch[i] 于是对于每一个询问分别计算就行了

100分做法:

其实40分的做法是提示你把每个询问拆成两份,一条链是向上和向下的,普通的话我们就可以对于lca这个点进行差分

分别统计向上的以及向下的

我们设起点终点以及路径上的一个点分别为s,t,v

向上的当且仅当deep[s]-deep[v]=watch[v]

向下的也是同理 deep[s]+deep[v]-2*deep[lca]=watch[v]

我们对这个式子进行移项


deep[s]=deep[v]+watch[v]

deep[s]-2*deep[lca]=watch[v]-deep[v]


容易观察到式子的右边是定值,于是我们对于每一个询问,用数据结构对左边的式子进行更新即可.

具体的讲一下我的做法吧

由于是对一条链的操作,我们用树链剖分O(n\log_2n)的复杂度肯定会t飞

所以我们可以利用一下树上差分的思想,并且用树链剖分来维护

只需要在这一条链上打标记就行了,这样用线段树来查询一个[L,R]就行了

对于线段树来说 维护一个线段树,对于每一个深度动态开点,于是就是一个单点打标记,区间查询的弱智线段树啦,可以用zkw达到常数上的优越

总复杂度


O(n\log_2n+m\log_2n)


我们把线段树换成桶,lca换成tarjan,就可以做到非常优秀的O(n+m) 的复杂度,待更..

2 thoughts on “noip2016day1t2天天爱跑步 树链剖分 线段树 or lca 桶

  1. 其实吧,lg表示的是以10为底的对数,而您的是以2为底。。。
    所以应该写:log2
    其实写log也可以
    但是lg专指log10
    文章还是很不错的
    Orz

    1. log不论底数,都只是相差了一个常数,因为使用渐进记号表示的,所以以十为底或以二为底都是同一个复杂度,怎么写都没关系的 🙂

发表评论

电子邮件地址不会被公开。 必填项已用*标注