给定长度为 $n\le10^5$ 的序列 $a$ ，统计满足以下条件的子区间数量

区间 $[l, r]$ 中，存在一个数 $x$ ，它的出现次数为 $m$，并且 $2m>r-l+1$

首先，树上差分是从子节点推到根节点，定义 $d$ 差分数组

若修改 $(x,y)$ 路径上的点权，则 $d_x, d_y \mathrel{+}= k, d_{\mathrm{lca}}, d_{\mathrm{fa}_{\mathrm{lca}}} \mathrel{-}= k$

1
2
3
4
5
6

void dfs(int u){
    val[u] = d[u];
    for (auto v : g[u]){
        dfs(v), val[u] += val[v];
    }
}

若修改 $(x,y)$ 路径上的边权，则 $d_x, d_y \mathrel{+}= k, d_{\mathrm{lca}}\mathrel{-}= 2k$

1
2
3
4
5
6
7
8

int dfs(int u){
    int ret = d[u];
    for (auto i : g[u]){
        i.w = dfs(i.v);
        ret += i.w;
    }
    return ret;
}

P3128 最大流