BZOJ4765 - [省选十连测R1T1]普通计算姬

2017/03/27

我好菜啊 _(:з」∠)_

一道非常厉害的分块题!

题目描述

给定一棵带标号、点权的有根树,设 表示点 i 的子树权值和。

每次两种操作:
1. 给定两个整数 U, V,修改点 U 的权值为 V 。
2. 给定两个整数 L, R,计算

点数
操作数

朴素做法

暴力取点的子树权值和:树状数组在 dfs 序上统计。

考虑对 进行 分块,统计出每个点对每个块的贡献。

询问复杂度
修改复杂度

复杂度貌似不对?
—— oscar2001

(其实可以卡过)

优化

维护 dfs 序:树状数组 分块

分块之后我们可以实现 查询一个子树和, 修改一个权值。

询问复杂度
修改复杂度

注意常熟优化。

还有就是求和的时候会超 LL,到处 ULL 可破。(数据里修改都是单增的

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#pragma GCC push_options
#pragma GCC optimize ("O3")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int PSIZ = 2E5 + 11;
const int MAXN = 1E5 + 11;
const int SPSIZ = 401;
typedef unsigned long long LL;

int N, M;
LL Val[PSIZ]; int Root;

int to[PSIZ], head[MAXN], nxt[PSIZ]; int ppos;
int ok[MAXN][SPSIZ]; int obelong[PSIZ];
int dfs1id, dfs1l, dfs1r;
void dfs1(int cur, int pre=0, int ref=0) {
    if(obelong[cur] == dfs1id) ref += 1;
    ok[dfs1id][cur] = ref;
    for(register int i=head[cur];i;i=nxt[i]) {
        int v = to[i];
        if(v != pre) {
            dfs1(v, cur, ref);
        }
    }
}

inline void _add(int u, int v) {
    ++ppos;
    nxt[ppos] = head[u];
    head[u] = ppos;
    to[ppos] = v;
}

void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

struct {
    int l, r;
    LL sum;
} oblock[SPSIZ]; int bpos = 0;

int L[PSIZ], R[PSIZ]; int T;
LL Src[PSIZ]; int ref[SPSIZ];
void dfs2(int cur, int pre=0) {
    L[cur] = ++T;
    Src[T] = Val[cur];
    ref[obelong[cur]]++;

    for(int i=1;i<=bpos;i++) ok[cur][i] = ref[i];

    for(int i=head[cur];i;i=nxt[i]) {
        int v = to[i];
        if(v != pre) {
            dfs2(v, cur);
        }
    }

    R[cur] = ++T;
    ref[obelong[cur]]--;
}

namespace blk {
    int belong[PSIZ];
    LL sum[PSIZ]; // Sum of [blk.L, i]
    struct {
        int l, r;
        LL sum; // Sum of [1, blk.L-1]
    } block[SPSIZ<<1]; int bpos = 0;

    void build() {
        int ps = int(sqrt(T));
        int end = 0;
        for(int i=1;i<=T;i++) {
            if(i == end+1) {
                bpos++; end += ps;
                block[bpos].l = i; block[bpos].r = end;
                block[bpos].sum += block[bpos-1].sum;
                sum[i] = Src[i];
            } else sum[i] = sum[i-1] + Src[i];

            belong[i] = bpos;
            block[bpos+1].sum += Src[i];
        }
        block[bpos].r = T;
    }

    void change(int x, LL dlt) {
        int bid = belong[x];
        for(int i=x;i<=block[bid].r;i++) {
            sum[i] += dlt;
        }
        for(int i=bid+1;i<=bpos;i++) {
            block[i].sum += dlt;
        }
    }

    LL presum(int x) { // Sum of [1, x]
        int bid = belong[x];
        return block[bid].sum + sum[x];
    }

    inline LL query(int l, int r) { // Sum of [L, R]
        return presum(r) - presum(l-1);
    }
};

int main() {
    scanf("%d %d", &N, &M);

    int ps = int(sqrt(N));
    int end = 0; // [1, ps], [ps+1, 2ps] ...
    for(int i=1;i<=N;i++) {
        if(i == end+1) {
            bpos++; end += ps;
            oblock[bpos].l = i, oblock[bpos].r = end;
        }
        scanf("%llu", &Val[i]);
        obelong[i] = bpos;
    }
    oblock[bpos].r = N;

    int u, v;
    for(int i=0;i<N;i++) {
        scanf("%d %d", &u, &v);
        if(u) addEdge(u, v);
        else Root = v;
    }

    dfs2(Root);
    blk :: build();

    for(int i=1;i<=bpos;i++) {
        for(int j=1;j<=N;j++) {
            oblock[i].sum += Val[j] * ok[j][i];
        }
    }

    LL op, a, b;
    for(int i=0;i<M;i++) {
        scanf("%llu %llu %llu", &op, &a, &b);
        if(op == 1) {
            LL dlt = b - Val[a];
            Val[a] = b;
            for(int j=1;j<=bpos;j++) {
                oblock[j].sum += dlt * ok[a][j];
            }
            blk :: change(L[a], dlt);
        } else {
            int bida = obelong[a], bidb = obelong[b];
            LL ans = 0;
            if(bida == bidb) {
                for(int j=a;j<=b;j++) ans += blk :: query(L[j], R[j]);
            } else {
                for(int j=a;j<=oblock[bida].r;j++) {
                    ans += blk :: query(L[j], R[j]);
                }
                for(int j=bida+1;j<bidb;j++) {
                    ans += oblock[j].sum;
                }
                for(int j=oblock[bidb].l;j<=b;j++) {
                    ans += blk :: query(L[j], R[j]);
                }
            }
            printf("%llu\n", ans);
        }
    }
}
#pragma GCC pop_options