朝田诗乃 的博客

朝田诗乃 的博客

题解 P3178 【[HAOI2015]树上操作】

posted on 2018-10-23 21:48:19 | under 题解 |

难道没有人喜欢代码短常数小时间快的可爱的树状数组吗?

这事一道树链剖分的板子题。我们先使用树链剖分将树上操作转化为区间操作。

对于操作1,直接修改区间[x, x]的值。

对于操作2,由于我们是dfs遍历树进行剖分,所以生成的序列在某种意义上相当于dfs序,所以以x为根的子树一定对应着剖分后序列中的连续区间,因此我们修改[x, x+siz[x]-1]区间的值即可。

对于操作3,用树剖板子中的路径求和在O(logn)的时间内求出答案。

由于操作仅涉及区间加减以及区间求和,所以这个东西可以用树状数组来维护。

什么?你以为树状数组只能单点修改、区间查询/单点查询、区间修改? ----> 『黑科技』树状数组实现区间修改与区间查询

短小又飞快的代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define MAXN 100050
#define lint long long
#define Re register
#define Finline __inline__ __attribute__ ((always_inline))
using namespace std;
Finline char get_char(){
    static char buf[20000001], *p1 = buf, *p2 = buf + fread(buf, 1, 2000000000, stdin);
    return p1 == p2 ? EOF : *p1++;
}
Finline void read(Re lint &x){
    char ch = getchar(); bool sign = 0;
    while(ch < '0' || ch > '9'){
        if(ch == '-') sign = 1;
        ch = getchar();
    }
    x = ch - 48;
    while(ch = getchar(), ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - 48;
    if(sign) x = -x;
}
Finline void write(Re lint x){
    if(x == 0) {putchar(48);return;}
    if(x < 0) putchar('-'), x = -x;
    int len = 0,dg[40];
    while(x > 0){dg[++len] = x % 10;x /= 10;}
    for(int i = len;i >= 1;i--) putchar(dg[i] + 48);
}
//===========输入输出优化==========
struct Edge {int to, next;} e[MAXN << 2];
lint h[MAXN], en, top[MAXN], fa[MAXN], dep[MAXN], siz[MAXN], heavyson[MAXN], n, q, w[MAXN], w2[MAXN];
lint t1[MAXN], t2[MAXN], id[MAXN], dfn;
Finline void addedge(Re int u, Re int v){
    e[en].to = v;
    e[en].next = h[u];
    h[u] = en++;
}

inline void dfs1(Re int u) {
    dep[u] = dep[fa[u]] + 1;
    siz[u] = 1;
    for(int v, i = h[u]; ~i; i = e[i].next) 
        if((v = e[i].to) != fa[u]){
            fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(!heavyson[u] || siz[heavyson[u]] < siz[v]) heavyson[u] = v;
        }
}

inline void dfs2(Re int u){
    id[u] = ++dfn;
    w2[id[u]] = w[u];
    if(!heavyson[u]) return;
    top[heavyson[u]] = top[u];
    dfs2(heavyson[u]);
    for(int v, i = h[u]; ~i; i = e[i].next)
        if((v = e[i].to) != fa[u] && v != heavyson[u])
            dfs2(top[v] = v);
}
//============树状数组===========
Finline void add(Re lint *c, Re lint x, Re lint val) {
    for(; x <= n; c[x] += val, x += x & (-x));
}
Finline lint findsum(Re lint *c, Re lint x) {
    lint res = 0;
    for(; x > 0; res += c[x], x -= x & (-x));
    return res;
}
Finline void update(Re int l, Re int r, Re lint val) {
    add(t1, l, val); add(t1, r+1, -val);
    add(t2, l, val*(l-1)); add(t2, r+1, -val*r);
}
Finline lint query(Re int l, Re int r){
    return r * findsum(t1, r) - (l-1) * findsum(t1, l-1) - findsum(t2, r) + findsum(t2, l-1);
}
Finline void build() {
    for(Re int i = 1;i <= n;i++){
        add(t1, i, w2[i] - w2[i-1]);
        add(t2, i, (i-1) * (w2[i] - w2[i-1]));
    }
}
//================================

Finline void rootadd(Re int u, Re lint val) {update(id[u], id[u] + siz[u] - 1, val);}
Finline lint ask(Re int x, Re int y) {
    lint res = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query(id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res += query(id[x], id[y]);
    return res;
}
int main()
{
    memset(h, -1, sizeof(h));
    read(n); read(q);
    lint u, v;
    lint k;
    for(Re int i = 1;i <= n;i++) read(w[i]);
    for(Re int i = 1;i < n;i++) {
        read(u); read(v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs1(fa[1] = 1);
    dfs2(top[1] = 1);
    build();
    lint opt;
    while(q--) {
        read(opt);
        if(opt == 1) {
            read(u); read(k);
            update(id[u], id[u], k);
        } else if(opt == 2){
            read(u); read(k);
            rootadd(u, k);
        } else {
            read(u);
            write(ask(1, u));
            putchar('\n');
        }
    }
}

总用时309ms,比线段树不知道快到哪里去了。