BZOJ 3626: [LNOI2014]LCA – [树链剖分/线段树]


题目传送门(BZOJ)
>原文链接<

题解 :

转自THU爷 gconeice 的题解,说的很明白

  1. 显然,暴力求解的复杂度是无法承受的。考虑这样的一种暴力,我们把 z 到根上的点全部打标记,对于 lr 之间的点,向上搜索到第一个有标记的点求出它的深度统计答案。观察到,深度其实就是上面有几个已标记了的点(包括自身)。所以,我们不妨把 z 到根的路径上的点全部+1,对于 lr 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现,实际上这个操作具有叠加性,且可逆。

也就是说我们可以对于 l 到 r 之间的点 i,将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点(包括自身)的权值和就是这个询问的答案。

  1. 把询问差分下,也就是用 [1, r] − [1, l − 1] 来计算答案,那么现在我们就有一个明显的解法。从 0n − 1 依次插入点 i,即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和,显然树链剖分或LCT均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n),LCT的复杂度为 O((n + q)· log n),均可以完成任务。

我写这题的时候忘记模了,咋调都调不出来 Orz

代码 :

#include 
#include 
#include 
#include 
#include 
#include 
#define ls p << 1
#define rs p << 1|1
#define mi ((l+r)>>1)
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
using namespace std;
char buf[100000], *p1, *p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
const int N = 101000;
const int P = 201314;
struct Edge {
    int to, val;
    Edge *next;
}*h[N],e[N<<1];
inline void Add_Edge(int u, int v, int w = 0) {
    static int _ = 0;
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
}
struct Query {
    int l, z, opt, id;
    bool operator < (const Query A) const {
        return l < A.l;
    } 
}q[N<<1];
int siz[N], top[N], fa[N], dep[N], son[N], cnt;
int ans[N], idx[N], t[N<<2], laz[N<<2], n, Q;
void dfs(int p) {
    dep[p] = dep[fa[p]]+1;
    siz[p] = 1;
    rev(i, p) if(i->to != fa[p]) {
        fa[i->to] = p;
        dfs(i->to);
        siz[p] += siz[i->to];
        if(siz[i->to] > siz[son[p]]) son[p] = i->to;
    }
}
void dfs(int p, int t) {
    idx[p] = ++*idx; top[p] = t;
    if(son[p]) dfs(son[p], t);
    rev(i, p) if(i->to != fa[p] && i->to != son[p]) {
        dfs(i->to, i->to);
    }
}
inline void pd(int l, int r, int p) {
    if(laz[p]) {
        int tmp = laz[p];
        (t[ls] += tmp*(mi-l+1)) %= P;
        (t[rs] += tmp*(r-mi)) %= P;
        (laz[ls] += tmp) %= P;
        (laz[rs] += tmp) %= P;
        laz[p] = 0;
    }
}
void change(int l, int r, int p, int x, int y, int c) {
    pd(l, r, p);
    if(x <= l && y >= r) {
        laz[p] = c;
        (t[p] += (r-l+1)*c) %= P;
        return ;
    }
    if(x <= mi) change(l, mi, ls, x, y, c);
    if(y > mi) change(mi+1, r, rs, x, y, c);
    t[p] = (t[ls]+t[rs])%P;
}
inline void insert(int x) {
    while(x) {
        change(1, n, 1, idx[top[x]], idx[x], 1);
        x = fa[top[x]];
    }
}
int query(int l, int r, int p, int x, int y) {
    pd(l, r, p);
    if(x <= l && y >= r) return t[p];
    int ret = 0;
    if(x <= mi) ret += query(l, mi, ls, x, y);
    if(y > mi) ret += query(mi+1, r, rs, x, y);
    return ret;
}
inline int query(int x) {
    int ret = 0;
    while(x) {
        (ret += query(1, n, 1, idx[top[x]], idx[x])) %= P;
        x = fa[top[x]];
    }
    return ret;
}
int main() {
    n = rd(), Q = rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = rd()+1;
        Add_Edge(i, u), Add_Edge(u, i);
    }
    for(int i = 1; i <= Q; i ++ ) {
        int l = rd(), r = rd()+1, z = rd()+1;
        q[++cnt].l = l, q[cnt].z = z, q[cnt].opt = -1, q[cnt].id = i;
        q[++cnt].l = r, q[cnt].z = z, q[cnt].opt = 1, q[cnt].id = i;
    }
    sort(q+1, q+cnt+1);
    dfs(1), dfs(1, 1);
    int now = 0;
    for(int i = 1; i <= cnt; i ++ ) {
        while(now < q[i].l && now <= n) insert(++now);
        ans[q[i].id] += q[i].opt*query(q[i].z);
    }
    for(int i = 1; i <= Q; i ++ ) printf("%d\n", (ans[i]%P+P)%P);
}

发表评论

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