朝田诗乃 的博客

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

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

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

#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) {
}
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));
lint u, v;
lint k;
for(Re int i = 1;i <= n;i++) read(w[i]);
for(Re int i = 1;i < n;i++) {
}
dfs1(fa[1] = 1);
dfs2(top[1] = 1);
build();
lint opt;
while(q--) {
if(opt == 1) {
update(id[u], id[u], k);
} else if(opt == 2){