bzoj4765: 普通计算姬（分块 && BIT）

最近一直在刷分块啊

似乎感觉分块和BIT是超级棒的搭档啊

这道题首先用dfs预处理一下

得到每一个sum值

此时查询是O(1)的 (前缀和乱搞什么的

但是修改需要O(n) （需要修改该节点所有祖先的sum

复杂度就爆了呀

此时考虑分块优化

似乎弹飞绵羊也是这样思考得出分块做法的

首先分成 √n 块

sum[i]记录第i块的sum和

中间的块直接用sum数组处理两边用树状数组暴力求

这样查询就是O（√n）的（其实有一些常数的... 就当是 √n 好了）

修改的话在dfs时用f[i][j]表示第j个点对于第i块的贡献（需要算几次什么的

然后直接修改块就好了复杂度也是O (√n) 的

下面是代码

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 using namespace std;

 #define isdigit(x) (x >= '0' && x <= '9')

 #define lowbit(x) (x & (-x))

 typedef unsigned long long ll;

 const int N = 1e5 + ;

 const int M = ;

 int n, root, cnt, sz, tot;

 int d[N], b[N], f[M][N], ct[N], L[N], p[N];

 ll     s[N], c[N];

 vector < int > E[N];

 inline void read(int &ans) {

     ans = ;

     register int res = ;

     static char buf = getchar();

     for (; !isdigit(buf); buf = getchar())

         if (buf == '-') res = -;

     for (; isdigit(buf); buf = getchar())

         ans = ans *  + buf - '';

     ans *= res;

 }

 inline void addEdge(int u ,int v) {

     E[u].push_back(v);

     E[v].push_back(u);

 }

 inline void add(int x, ll v) {

     while (x <= n) {

         c[x] += v;

         x += lowbit(x);

     }

 }

 inline ll query(int x) {

     ll ans = ;

     while (x > ) {

         ans += c[x];

         x -= lowbit(x);

     }

     return ans;

 }

 ll dfs(int x, int fa) {

     ll sum = d[x]; p[x] = ++tot;

     ct[b[x]]++; add(tot, d[x]);

     for (int i = ; i <= cnt; i++)   f[i][x] += ct[i];

     for (int i = ; i < E[x].size(); i++) {

         int u = E[x][i];

         if (u == fa)    continue;

         sum += dfs(u, x);

     }

     ct[b[x]]--; L[x] = tot;

     s[b[x]] += sum;

     return sum;

 }    

 inline void modify(int u, int v) {

     add(p[u], v - d[u]);

     for (int i = ; i <= cnt; i++)

         s[i] += (v - d[u]) * 1ll * f[i][u];

     d[u] = v;

 }

 inline ll query(int l ,int r) {

     ll ans = ;

     if (b[l] == b[r]) {

         for (int i = l; i <= r; i++)

             ans += query(L[i]) - query(p[i] - );

         return ans;

     }

     for (int i = b[l] + ; i < b[r]; i++)

         ans += s[i];

     for (int i = l; i <= b[l] * sz; i++)

         ans += query(L[i]) - query(p[i] - );

     for (int i = (b[r] - ) * sz + ; i <= r; i++)

         ans += query(L[i]) - query(p[i] - );

     return ans;

 }

 int main() {

     int m;

     read(n); read(m);

     sz = sqrt(n);

     for (int i = ; i <= n; i++) {

         read(d[i]);

         b[i] = (i - ) / sz + ;

     }

     cnt = b[n];

     for (int i = ; i <= n; i++) {

         int u, v;

         read(u); read(v);

         if (!u)    root = v;

         else addEdge(u, v);

     }

     dfs(root, );

     while (m--) {

         int op, u, v;

         read(op); read(u); read(v);

         if (op == )

             modify(u, v);

         else

             printf("%llu\n", query(u, v));

     }

     return ;

 }

巴特西

bzoj4765: 普通计算姬（分块 && BIT）

最新文章

热门文章

巴特西

bzoj4765: 普通计算姬 （分块 && BIT）

最新文章

热门文章

bzoj4765: 普通计算姬（分块 && BIT）