SCOI2015 情报传递

树链剖分

LOJ
这里写的是两个 log 的做法。
首先如果一个情报员是危险的，就有 当前时间-c>情报员的开始时间。也就是统计一条路径上小于某个数的数的个数，使用轻重链剖分+树状数组。注意这里的树状数组维护不再是权值，而是答案的个数。所以将每个询问按照 $i-c$ 的大小排序，离线的搞。
常数貌似很小，Luogu 跑到第一版去了（23333

#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAXN = 2e5;
int n, q, tot1, tot2, edge, tim, root;
int dfn[MAXN | 1], son[MAXN | 1], size[MAXN | 1], topf[MAXN | 1], depth[MAXN | 1], father[MAXN | 1], bit[MAXN | 1];
struct Edge {
    int to;
    Edge *nxt;
    Edge(void) {}
    Edge(Edge *x, int y) : nxt(x), to(y) {}
} e[MAXN], *firstEdge[MAXN | 1];
struct Query {
    int x, y, c, id, ans, sum;
    Query(void) {}
} a[MAXN | 1];
struct Modify {
    int id, t;
    Modify(void) {}
} b[MAXN | 1];
inline int read() {
     register int x = 0;
     register char ch = getchar();
     while(!isdigit(ch)) ch = getchar();
     while(isdigit(ch)) {
         x = x * 10 + ch - '0';
         ch = getchar();
     }
     return x;
}
inline void addEdge(int x, int y) {
    e[++edge] = Edge(firstEdge[x], y);
    firstEdge[x] = &e[edge];
}
bool comp1(Query x, Query y) {
    return x.id - x.c < y.id - y.c;
}
bool comp2(Query x, Query y) {
    return x.id < y.id;
}
void dfs1(int x, int fa) {
    father[x] = fa;
    depth[x] = depth[fa] + 1;
    size[x] = 1;
    for(Edge *k = firstEdge[x]; k; k = k -> nxt) {
        int to = k -> to;
        if(to == fa) continue;
        dfs1(to, x);
        size[x] += size[to];
        if(size[to] > size[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int ftop) {
    dfn[x] = ++tim;
    topf[x] = ftop;
    if(!son[x]) return;
    dfs2(son[x], ftop);
    for(Edge *k = firstEdge[x]; k; k = k -> nxt) {
        int to = k -> to;
        if(to != son[x] && to != father[x]) dfs2(to, to);
    }
}
inline void modify(int x) {
    while(x <= n) {
        ++bit[x];
        x += x & (-x);
    }
}
inline int query(int x) {
    int res = 0;
    while(x > 0) {
        res += bit[x];
        x -= x & (-x);
    }
    return res;
}
inline int queryRange(int i) {
    int x = a[i].x, y = a[i].y;
    while(topf[x] != topf[y]) {
        if(depth[topf[x]] < depth[topf[y]]) std::swap(x, y);
        a[i].ans += query(dfn[x]) - query(dfn[topf[x]] - 1);
        x = father[topf[x]];
    }
    if(depth[x] > depth[y]) std::swap(x, y);
    a[i].ans = a[i].ans + query(dfn[y]) - query(dfn[x] - 1);
    a[i].sum += depth[a[i].x] - depth[x] + depth[a[i].y] - depth[x] + 1;
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++i) {
        int a = read();
        if(a == 0) root = i;
        else addEdge(a, i);
    }
    dfs1(root, 0);
    dfs2(root, root);
    q = read();
    for(int i = 1; i <= q; ++i) {
        int opt = read();
        if(opt == 1) {
            ++tot1;
            a[tot1].x = read();
            a[tot1].y = read();
            a[tot1].c = read();
            a[tot1].id = i;
            a[tot1].sum = a[tot1].ans = 0;
        } else {
            ++tot2;
            b[tot2].t = read();
            b[tot2].id = i;
        }
    }
    std::sort(a + 1, a + 1 + tot1, comp1);
    int tail = 0;
    for(int i = 1; i <= tot1; ++i) {
        while(tail < tot2 && b[tail + 1].id < a[i].id - a[i].c) {
            modify(dfn[b[tail + 1].t]);
            ++tail;
        }
        queryRange(i);
    }
    std::sort(a + 1, a + 1 + tot1, comp2);
    for(int i = 1; i <= tot1; ++i) printf("%d %d\n", a[i].sum, a[i].ans);
    return 0;
}