进行一个转化：

原序列上每个点代表 dfs 序列（权值）上的区间和。

首先把区间和差分成两个前缀和。

然后分块，块内维护点序列dfs序前缀和。单点加操作发生时，只影响每个块内包含这个位置的前缀和。

因而统计块内每种长度出现次数的后缀和，就能 $\mathcal{O}(1)$ 查询每个修改贡献到了哪几个查询，从而对整块的答案求出变化量。

要开 unsigned long long。

注意这个转化是更强的一个问题。

但是分块写起来挺清楚的。

改了一下 cc 题 chef and churu 的 code。

const int maxn = 1e5 + 10, bs = 316, nb = maxn / bs + 1;
struct seq {
    int n;
    ll a[maxn + 10], preS[maxn + 10], tag[nb + 10];
    void init(int _n) {
        n = _n;
        rep(i,1,n) preS[i] = preS[i - 1] + a[i];
    }
    void inc(int x, int c) {
        int bx = gb(x);
        per(i,gb(n),bx+1) tag[i] += c;
        per(i,eob(bx),x) preS[i] += c;
        a[x] += c;
    }
    ll qry(int x) { return preS[x] + tag[gb(x)]; }
} sq;

struct block {
    int a[maxn + 10], bcnt[nb + 10][maxn + 10], n;
    ll tag[maxn + 10], sum[maxn + 10];
    void init(int _n) {
        n = _n;
        rep(i,gb(1),gb(n)) {
            int s = hob(i), t = eob(i); sum[i] = 0;
            rep(j,s,t) ++ bcnt[i][a[j]], sum[i] += sq.preS[a[j]];
            per(j,n - 1,1) bcnt[i][j] += bcnt[i][j + 1];
        }
    }
    void modify(int x, int ac) {
        rep(i,gb(1),gb(n)) sum[i] += 1ll * bcnt[i][x] * ac;
    }
    ll qry(int l, int r) {
        return r == 1 ? _qry(r) : _qry(r) - _qry(l - 1);
    }
    ll _qry(int x) {
        ll ret = 0;
        int bx = gb(x);
        rep(i,0,bx - 1) ret += sum[i];
        rep(i,hob(bx),x) ret += sq.qry(a[i]);
        return ret;
    }
} blker[2];

vector< vector<int> > g;

vector<int> a, idfn, siz;
int dfs_clock = 0;
void dfs(int cur, int pre) {
    sq.a[++ dfs_clock] = a[cur]; idfn[cur] = dfs_clock;
    siz[cur] = 1;
    for(int ver : g[cur]) if(ver != pre) {
            dfs(ver, cur);
            siz[cur] += siz[ver];
        }
}

signed main() {
    int n, m;
    scanf("%d %d", &n, &m);
    g.resize(n + 1);
    idfn.resize(n + 1);
    a.resize(n + 1);
    siz.resize(n + 1);
    rep(i,1,n) scanf("%d", &a[i]);
    int root = 0, u, v;
    rep(i,1,n) {
        scanf("%d %d", &u, &v);
        if(u) {
            g[u].push_back(v);
            g[v].push_back(u);
        } else root = v;
    }
    dfs(root, 0);
    sq.init(n);
    rep(i,1,n) {
        blker[0].a[i] = idfn[i] + siz[i] - 1;
        blker[1].a[i] = idfn[i] - 1;
    }
    blker[0].init(n);
    blker[1].init(n);
    int op, l, r;
    rep(qr,1,m) {
        scanf("%d %d %d", &op, &l, &r);
        if(op == 1) {
            int ic = r - a[l]; a[l] = r;
            sq.inc(idfn[l], ic);
            blker[0].modify(idfn[l], ic);
            blker[1].modify(idfn[l], ic);
        } else {
            printf("%llu\n", blker[0].qry(l, r) - blker[1].qry(l, r));
        }
    }
    return 0;
}

。

思路

为什么这题机房内部、网上人均分块啊......

注意到转成括号序后是 [Ynoi2077] 3dmq 的严格弱化版，甚至也是 "2dmq" 的弱化版，于是乎你可以暴力用严格 $O(n\sqrt n)$ 的 kdt。

嘴巴一下如何优化复杂度。

对左右括号分讨，可以转换为矩形加矩形查询，并且矩形加有一维无界，矩形求和另一维无界。

于是这题（似乎）可以 polylog 了。其实我也不会，是嘴巴的。（感觉是假的）

打了一个 kdt 的版本，时限 3s，在 Hydro-bzoj 很容易就过了。

polylog 做法有兴趣的同学自行实现吧。

Code

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
struct point{uint x,y;ullt a,v;};
struct node
{
	point p;uint Maxx,Minx,Maxy,Miny;ullt sum,lazy,suma;node*L,*R;
	node(point*bgn,point*end,bol op):lazy(0),L(NULL),R(NULL)
	{
		point*mid=bgn+((end-bgn)>>1);
		std::nth_element(bgn,mid,end,[=](point a,point b){return op?a.x<b.x:a.y<b.y;});
		p=*mid,Maxx=Minx=p.x,Maxy=Miny=p.y,sum=p.v,suma=p.a;
		if(bgn!=mid)L=new node(bgn,mid,!op),
			_max(Maxx,L->Maxx),_max(Maxy,L->Maxy),
			_min(Minx,L->Minx),_min(Miny,L->Miny),
			sum+=L->sum,suma+=L->suma;
		if(mid+1!=end)R=new node(mid+1,end,!op),
			_max(Maxx,R->Maxx),_max(Maxy,R->Maxy),
			_min(Minx,R->Minx),_min(Miny,R->Miny),
			sum+=R->sum,suma+=R->suma;
	}
	voi pushdown()
	{
		if(L!=NULL)L->sum+=lazy*L->suma,L->lazy+=lazy,L->p.v+=lazy*L->p.a;
		if(R!=NULL)R->sum+=lazy*R->suma,R->lazy+=lazy,R->p.v+=lazy*R->p.a;
		lazy=0;
	}
	voi pushup()
	{
		pushdown(),sum=p.v;
		if(L!=NULL)sum+=L->sum;
		if(R!=NULL)sum+=R->sum;
	}
	voi add(uint r,ullt w)
	{
		if(Minx>r)return;
		if(Maxx<=r){lazy+=w,p.v+=w*p.a,sum+=w*suma;return;}
		if(p.x<=r)p.v+=w*p.a;
		if(L!=NULL)L->add(r,w);
		if(R!=NULL)R->add(r,w);
		pushup();
	}
	ullt find(uint l,uint r)
	{
		if(Miny>=r||Maxy<l)return 0;
		if(Miny>=l&&Maxy<r)return sum;
		pushdown();
		ullt ans=0;
		if(p.y>=l&&p.y<r)ans=p.v;
		if(L!=NULL)ans+=L->find(l,r);
		if(R!=NULL)ans+=R->find(l,r);
		return ans;
	}
};
std::vector<uint>Way[300005];ullt A[300005];point P[300005];uint Dfn[300005];
uint cnt;
voi dfs(uint p,uint f)
{
	P[p<<1].x=Dfn[p]=cnt++,P[p<<1].v=A[p];
	for(auto s:Way[p])if(s!=f)dfs(s,p),P[p<<1].v+=P[s<<1].v;
	P[p<<1|1].x=cnt++;
}
int main()
{
	uint n,m,rt=0;scanf("%u%u",&n,&m);
	for(uint i=0;i<n;i++)scanf("%llu",A+i),P[i<<1].y=P[i<<1|1].y=i,P[i<<1].a=1llu,P[i<<1|1].a=-1llu;
	for(uint i=0;i<n;i++){uint u,v;scanf("%u%u",&u,&v);if(u)Way[--u].push_back(--v),Way[v].push_back(u);else rt=v-1;}
	dfs(rt,-1);
	node T(P,P+(n<<1),0);
	while(m--)
	{
		uint op;scanf("%u",&op);
		if(op==1){uint p;ullt v;scanf("%u%llu",&p,&v),p--;T.add(Dfn[p],v-A[p]),A[p]=v;}
		else{uint l,r;scanf("%u%u",&l,&r),printf("%llu\n",T.find(l-1,r));}
	}
	return 0;
}