点分治水题

遇事不决点分治

Posted by ethan-zhou on December 5, 2021

CF1260F Colored Tree

题意

一颗有 n 个节点的树,每个节点 v 有颜色 $c_v$,这个染色方案的权值为 $\sum\limits_{u,v\in[1,n],v>u,c_v=c_u}\operatorname{dis}{(u,v)}$。

现在知道每个节点 v 可以染成 $[l_v,r_v]$ 中任意颜色,求所有染色方案的权值之和。

$n\le 10^5$,时限 2.5 秒。

思路

一个显然的想法是考虑每一条路径的贡献,于是自然的想到点分治。考虑过分治中心一条路径的贡献(为方便起见,后文都算的是权值期望)。

显然贡献为:

\[(d_u+d_v)\frac{|[l_u,r_u]\cap[l_v,r_v]|}{|[l_u,r_u]|\cdot|[l_v,r_v]|}\]

我们可以维护一个线段树,在搜到 u 的时,把 $[l_u,r_u]$ 区间加 $\frac{d_u}{|[l_u,r_u]|}$。搜到 v 时,把 $[l_v,r_v]$ 区间的和,乘以 $\frac1{|[l_v,r_v]|}$,加到答案里即可,这样我们就解决了上式中第一项。

对于第二项,可以反着做一遍,也可以再开一个另外含义的线段树,怎么搞都行。

复杂度 $\mathcal{O}(n\log^2 n)$。

题解提供了一个不用点分治的做法,复杂度一样,在此先不说,因为我没读懂。

代码

const ll INF=1e18,P=1e9+7;

inline ll mod(ll x){
    if(x>=P)return x-P;
    if(x<0)return x+P;
    return x;
}
inline ll qpow(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%P;x=x*x%P;y>>=1;}return res;}

const ll MXN=1e5+5,MNMEM=5e4;

ll n,ans,all=1,arr[MXN],lh[MXN],rh[MXN];
struct tarr{
    ll d[MXN],di[MXN];
    inline void suf(ll x,ll y){
        ll yi=y*x%P;
        for(;x<MXN;x+=x&(-x)){
            d[x]=mod(d[x]+y);
            di[x]=mod(di[x]+yi);
        }
    }
    inline ll pre(ll l){
        ll s=0,si=0;
        for(ll x=l;x;x^=x&(-x)){
            s=mod(s+d[x]);
            si=mod(si+di[x]);
        }
        return (s*(l+1)-si)%P;
    }
    inline void clr(ll x){for(;x<MXN;x+=x&(-x))d[x]=di[x]=0;}
    inline void mem(){
        memset(d,0,sizeof(d));
        memset(di,0,sizeof(di));
    }
}c,v;

vector<ll> t[MXN];
ll sz[MXN];bool vis[MXN];
inline void dfssz(ll p,ll fa){
    sz[p]=1;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa){
            dfssz(nx,p);
            sz[p]+=sz[nx];
        }
}
inline ll dfsrt(ll p,ll fa,ll tot){
    bool f=(sz[p]<<1)>=tot;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa){
            ll tmp=dfsrt(nx,p,tot);
            if(tmp)return tmp;
            f&=(sz[nx]<<1)<=tot;
        }
    return f?p:0;
}
inline void dfsm(ll p,ll fa,ll dpth){
    if(dpth<0){
        c.clr(lh[p]),c.clr(rh[p]+1);
        v.clr(lh[p]),v.clr(rh[p]+1);
    }
    else{
        ll tmp=dpth*arr[p]%P;
        c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
        v.suf(lh[p],tmp),v.suf(rh[p]+1,-tmp);
    }
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa)
            dfsm(nx,p,dpth+1);
}
inline void dfsq(ll p,ll fa,ll dpth){
    ans=(ans+(dpth*(c.pre(rh[p])-c.pre(lh[p]-1))+v.pre(rh[p])-v.pre(lh[p]-1))%P*arr[p])%P;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa)
            dfsq(nx,p,dpth+1);
}

inline void dfz(ll p){
    dfssz(p,0);
    ll tsz=sz[p];
    vis[p=dfsrt(p,0,tsz)]=1;

    c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
    for(ll &nx:t[p])
        if(!vis[nx]){
            dfsq(nx,0,1);
            dfsm(nx,0,1);
        }
    if(tsz>MNMEM)c.mem(),v.mem();
    else dfsm(p,0,-INF);
    for(ll &nx:t[p])
        if(!vis[nx])
            dfz(nx);
}

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",lh+i,rh+i);
        arr[i]=qpow(rh[i]-lh[i]+1,P-2);
        all=all*(rh[i]-lh[i]+1)%P;
    }
    for(ll i=1,ts,tt;i<n;i++){
        scanf("%lld%lld",&ts,&tt);
        t[ts].pb(tt);
        t[tt].pb(ts);
    }
    dfz(1);

    printf("%lld\n",all*(ans+P)%P);
    return 0;
}

树上游戏

实在找不到啥点分治好题了,只能用点分治硬做这题。

题意

树上每个点有颜色,定义 $\operatorname{s}{(i,j)}$ 为 i 到 j 路径颜色数,对于 $i\in[1,n]$ 求 $ans_i=\sum\limits_{j\in[1,n]}\operatorname{s}{(i,j)}$。

$n\le10^5$,时限 1 秒。

思路

这题怎么做都行,有好多线性的做法,但是我们要有拿下最劣解的追求,为了实现这一目标,考虑淀粉质的做法。

上图中,蓝色大三角表示所有搜过的子树,v 是正在查询的点,对于所有过分治中心 rt 的路径 $u \sim v$,考虑红色对哪些路径有贡献,发现有两种情况:

  • u 在某个红色节点的子树中
  • $v \sim rt$ 上有红色节点

定义 hasc 表示(蓝色子树中)到 rt 的路径上有红色的点数,当我修改节点 u 的时候,如果发现路径 $rt\sim u$ 上没有红色的话,我就 $hasc\gets hasc + \text{u 子树大小}$。

在查询时,一开始的答案为 hasc ,dfs 的过程中,如果第一次碰到一个红色点(这个点的祖先上没有红色点),那么对于其子树,红色的贡献就增加了蓝色区域的点数,回溯的时候再撤销即可。

因为每个点只有一个颜色,所以其实上述的过程是可以在 dfs 中对每个颜色同时进行的。

复杂度 $O(n\log n)$。

有不少细节,尤其是在分治中心的处理上,不建议实现。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MXN = 1e5 + 5;
ll n, c[MXN];
vector<ll> g[MXN];

bool vis[MXN];
ll sz[MXN];
void dfssz(ll p, ll fa) {
    sz[p] = 1;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) {
            dfssz(nx, p);
            sz[p] += sz[nx];
        }
}
ll dfsrt(ll p, ll fa, ll tot) {
    bool f = (sz[p] << 1) >= tot;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) {
            ll nxr = dfsrt(nx, p, tot);
            if (nxr) return nxr;
            f &= (sz[nx] << 1) <= tot;
        }
    return f ? p : 0;
}

ll instk[MXN], ans[MXN];
//到根路径上有这个颜色的节点数
ll hasc[MXN], curans;
void dfsm(ll p, ll fa, ll tp) {
    if (!instk[c[p]]++) {
        hasc[c[p]] += tp * sz[p];
        curans += tp * sz[p];
    }
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) dfsm(nx, p, tp);
    --instk[c[p]];
}
void dfsq(ll p, ll fa, ll outofsubt) {
    if (!instk[c[p]]++) curans += outofsubt - hasc[c[p]];
    ans[p] += curans;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) dfsq(nx, p, outofsubt);
    if (!--instk[c[p]]) curans -= outofsubt - hasc[c[p]];
}
void dfz(ll p) {
    dfssz(p, 0);
    p = dfsrt(p, 0, sz[p]);
    vis[p] = 1;
    dfssz(p, 0);

    instk[c[p]] = 1;
    for (ll nx : g[p])
        if (!vis[nx]) dfsm(nx, p, 1);
    //到根
    ans[p] += curans + sz[p];
    for (ll nx : g[p])
        if (!vis[nx]) {
            dfsm(nx, p, -1);
            curans += sz[p] - sz[nx];
            dfsq(nx, p, sz[p] - sz[nx]);
            curans -= sz[p] - sz[nx];
            dfsm(nx, p, 1);
        }
    for (ll nx : g[p])
        if (!vis[nx]) dfsm(nx, p, -1);
    instk[c[p]] = 0;
    for (ll nx : g[p])
        if (!vis[nx]) dfz(nx);
}
int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", c + i);
    for (ll i = 1; i < n; i++) {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfz(1);
    for (ll i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;
}

P3060 [USACO12NOV]Balanced Trees G

题意

给出一棵树,每个节点上有一个括号,对于所有括号匹配的路径,求其嵌套层数最大值。

思路

括号匹配比较有用的性质就是把 { 看成 1,} 看成 -1,最终序列的前缀和 $pre_i$都大于等于 0,并且总和 s 为 0.

而最大嵌套层数则等于前缀和的最大值。

考虑把两个括号序列合起来:

\[\begin{aligned} str&=str1 + str2\cr s&=s1+s2\cr \max{(pre_i)}&=\max{(\max{(pre1_i)},s1+\max{(pre2_i)})}\cr \min{(pre_i)}&=\min{(\min{(pre1_i)},s1+\min{(pre2_i)})} \end{aligned}\]

所以只需在第一次 dfs 时,判断如果前半段 pre 的最小值大于等于 0,就把前半段 pre 的最大值打到一个桶里 s1 的位置,查询就随便搞搞即可。

没时间实现了,我妈催我睡觉😡。


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon