合理平衡复杂度是手筋

懵逼的 题目

qwq

扯淡的 题解

不会, 抄的题解

来…让我们想一下 树链剖分一次修改的复杂度是$\mathrm O(\lg n)$, 但是查询是$\mathrm O(n)$的

好…那我们就可以平衡复杂度了

考虑一下修改一个点对答案的贡献, 修改一个节点的权值只会对他的祖先造成影响, 我们就可以搞一个区间求和的大分块, 记录最后的ans, 然后搞一个数组g[i][j], 表示第$i$个节点在第$j$个块有几个祖先(包括自己), 这样修改的时候就可以直接sum[i] += g[dq][i] * zh

那么零散的块呢? 总不能搞一个树链剖分吧…

Emmmmm…如果我们不记录子树和, 而是每一次都重新计算呢?

在$dfs$序上搞一个树状数组, 然后每一次都重新计算子树和!

完美!

感觉再给我三辈子我也想不出来_(:з」∠)_

好…让我们想想我们需要些什么…

  • 一个区间修改, 区间查询的块qwq, 用来存储最终的答案
    • 一个数组sum[MAXK], 记录当前块的数字和; 一个单点修改, 区间查询的树状数组b, 建在$dfs$序上, 用来存储每一个节点的子树和
    • ULL cx(int le, int ri):
      • 找到$[le, ri]$间的整块, re += sum[i]
      • 对于所有的零散点, re += cxsum(i)
    • void xg(int wz, ULL zh): 遍历所有的块, sum[i] += zh * g[wz][i], xgsum(ta[wz].begin, zh)
  • 一个数组g[MAXN][MAXK]: g[i][j]用来存储第i个节点在第j个块中的祖先个数(用来记录贡献)
  • 一个结构体ta[MAXN] = {begin, end}, 来搞$dfs$序

沙茶的 代码

注意几个细节:

  • 分块的时候一定要在最后一个块的右边界上加一个和$n$的取$\min$…否则$RE$死你…
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXK (350 + 5)
#define INF (0x7ffffff)
#define lowbit(x) ((x) & (-(x)))
#define ULL unsigned long long
#define LL long long
#define rint register int 
#define cint const int 
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct edg
{
    int from, to, next;
}tb[MAXN << 1];
struct tnode
{
    int begin, end, fa;
}ta[MAXN];
int n, root, tg[MAXN], g[MAXN][MAXK], cnta, cntb, block, le[MAXK], ri[MAXK];
ULL sum[MAXK], b[MAXN];
LL a[MAXN];
inline int belong(int x)
{ return ((x - 1) / block + 1); }
inline ULL cxsum(int x)
{
    ULL re = 0;
    for (int i = ta[x].end; i; i -= lowbit(i))
        re += b[i];
    for (int i = ta[x].begin - 1; i; i -= lowbit(i))
        re -= b[i];
    return re;
}
inline void xgsum(int wz, LL zh)
{
    for (int i = wz; i <= n; i += lowbit(i))
        b[i] += zh;
}
void dfs(int dq)
{
    ta[dq].begin = ++cnta;
    xgsum(cnta, a[dq]);
    for (int i = 1; i <= le[0]; i++)
        g[dq][i] = g[ta[dq].fa][i];
    ++g[dq][belong(dq)];
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            dfs(tb[i].to);
        }
    ta[dq].end = cnta;
}
void xg(int wz, LL zh)
{
    a[wz] += zh;
    for (int i = 1; i <= le[0]; i++)
        sum[i] += zh * g[wz][i];
    xgsum(ta[wz].begin, zh);
}
ULL cx(int l, int r)
{
    ULL re = 0;
    int lerk = INF, rigk = -INF;
    for (int i = 1; i <= le[0]; i++)
        if (le[i] >= l && ri[i] <= r)
        {
            re += sum[i];
            lerk = min(lerk, i), rigk = max(rigk, i);
        }
    if (lerk >= INF || rigk < 0)
    {
        for (int i = l; i <= r; i++)
            re += cxsum(i);
        return re;
    }
    if (lerk > 1)
        for (int i = l; i <= ri[lerk - 1]; i++)
            re += cxsum(i);
    if (rigk < le[0])
        for (int i = le[rigk + 1]; i <= r; i++)
            re += cxsum(i);
    return re;
}
void init()
{
    block = sqrt(n) + 1;
    for (int i = 1; i <= n; i += block)
        le[++le[0]] = i, ri[++ri[0]] = min(n, i + block - 1);
}
void adn(int from, int to)
{
    tb[++cntb].next = tg[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    tg[from] = cntb;
}
int main()
{
    freopen("in.in", "r", stdin);
    int q;
    scanf("%d%d", &n, &q);
    init();
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1, srx, sry; i <= n; i++)
    {
        scanf("%d%d", &srx, &sry);
        if (!srx)
        {
            root = sry;
            continue;
        }
        adn(srx, sry);
        adn(sry, srx);
    }
    ta[root].fa = root;
    dfs(root);
    for (int i = 1; i <= le[0]; i++)
        for (int j = le[i]; j <= ri[i]; j++)
            sum[i] += cxsum(j);
    for (int i = 1, sre, srx, sry; i <= q; i++)
    {
        scanf("%d%d%d", &sre, &srx, &sry);
        if (sre == 1)
            xg(srx, sry - a[srx]);
        else
            printf("%llu\n", cx(srx, sry));
    }
    return 0;
}

By 大傻叉 Cansult