pushdown tag[rs]漏了个加号
by L_cm_C5H6 @ 2022-03-29 14:40:10
@[L_cm_C5H6](/user/429699)
```cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define PB push_back
using namespace std;
const int N = 3E5+5,M = 6E5+10;
ll n,m;
vector<ll > g[N];
ll fa[N],siz[N],dep[N],son[N],top[N];
inline void dfs1(ll u,ll far,ll depth)
{
siz[u] = 1;
fa[u] = far;
dep[u] = depth;
rep(i,0,g[u].size())
{
ll v = g[u][i];
if(v==far) continue;
dfs1(v,u,depth+1);
siz[u] += siz[v];
if(siz[v]>siz[son[u]]) son[u] = v;
}
}
ll val[N],val0[N],id[N],cnt;
inline void dfs2(ll u,ll top0)
{
id[u] = ++cnt;
val[cnt] = val0[u];
top[u] = top0;
if(!son[u]) return ;
dfs2(son[u],top0);
rep(i,0,g[u].size())
{
int v = g[u][i];
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
struct node{
ll l,r,sum,tag;
ll len()
{
return r-l+1;
}
}tr[N<<2];
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(int u)
{
tr[u<<1].tag += tr[u].tag;
tr[u<<1|1].tag += tr[u].tag;
tr[u<<1].sum += tr[u<<1].len()*tr[u].tag;
tr[u<<1|1].sum += tr[u<<1|1].len()*tr[u].tag;
tr[u].tag = 0;
}
inline void build(ll u,ll l,ll r)
{
if(l==r)
{
// cout<<"build: "<<val[l]<<endl;
tr[u] = {l,r,val[l],0};
return ;
}
int mid = l + r >> 1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
inline ll query(ll u,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)
return tr[u].sum;
ll mid = l + r >> 1;
ll res = 0;
if(tr[u].tag) pushdown(u);
if(L<=mid) res += query(u<<1,l,mid,L,R);
if(mid+1<=R) res += query(u<<1|1,mid+1,r,L,R);
return res;
}
inline void update(ll u,ll l,ll r,ll L,ll R,ll k)
{
if(L<=l&&r<=R)
{
tr[u].tag += k;
tr[u].sum += k*tr[u].len();
// cout<<"up: "<<u<<" "<<l<<" "<<r<<" "<<tr[u].sum<<endl;
}
else
{
if(tr[u].tag) pushdown(u);
ll mid = l + r >> 1;
if(L<=mid) update(u<<1,l,mid,L,R,k);
if(R>=mid+1) update(u<<1|1,mid+1,r,L,R,k);
pushup(u);
}
}
inline ll qRange(ll x,ll y)
{
ll ans = 0;// cout<<"qRange"<<endl;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ll temp = query(1,1,n,id[top[x]],id[x]);
ans += temp;
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return ans + query(1,1,n,id[x],id[y]);
}
inline void upSon(ll u,ll k)
{
update(1,1,n,id[u],id[u]+siz[u]-1,k);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
repd(i,1,n) cin>>val0[i];
repd(i,1,n-1)
{
int u,v;
cin>>u>>v;
g[u].PB(v);g[v].PB(u);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
repd(i,1,m)
{ //cout<<">>>"<<endl;
ll opt,x,y;
cin>>opt;
if(opt==1)
{
cin>>x>>y;
update(1,1,n,id[x],id[x],y);
}
else if(opt==2)
{
cin>>x>>y;
upSon(x,y);
}
else if(opt==3)
{
cin>>x;
cout<<qRange(1,x)<<endl;
}
}
return 0;
}
```
谢谢，但还是不行
by BeautifulWater @ 2022-03-29 14:52:33
build写炸了 两个区间以上没有管理到
把初值拉到最前面后能过样例
~~假如还是不能过题把dfs1参数全改1看看~~
by L_cm_C5H6 @ 2022-03-29 15:13:17
@[L_cm_C5H6](/user/429699)
漏了对一些区间长度不为一的区间的初始化，谢谢大佬
```cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define PB push_back
using namespace std;
const int N = 1E6+500,M = 6E5+10;
ll n,m;
vector<ll > g[N];
ll fa[N],siz[N],dep[N],son[N],top[N];
inline void dfs1(ll u,ll far,ll depth)
{
siz[u] = 1;
fa[u] = far;
dep[u] = depth;
rep(i,0,g[u].size())
{
ll v = g[u][i];
if(v==far) continue;
dfs1(v,u,depth+1);
siz[u] += siz[v];
if(siz[v]>siz[son[u]]) son[u] = v;
}
}
ll val[N],val0[N],id[N],cnt;
inline void dfs2(ll u,ll top0)
{
id[u] = ++cnt;
val[cnt] = val0[u];
top[u] = top0;
if(!son[u]) return ;
dfs2(son[u],top0);
rep(i,0,g[u].size())
{
int v = g[u][i];
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
struct node{
ll l,r,sum,tag;
ll len()
{
return r-l+1;
}
}tr[N<<2];
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(int u)
{
tr[u<<1].tag += tr[u].tag;
tr[u<<1|1].tag += tr[u].tag;
tr[u<<1].sum += tr[u<<1].len()*tr[u].tag;
tr[u<<1|1].sum += tr[u<<1|1].len()*tr[u].tag;
tr[u].tag = 0;
}
inline void build(ll u,ll l,ll r)
{
if(l==r)
{
// cout<<"build: "<<val[l]<<endl;
tr[u] = {l,r,val[l],0};
return ;
}
int mid = l + r >> 1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
tr[u] = {l,r,0,0};
pushup(u);
}
inline ll query(ll u,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)
return tr[u].sum;
ll mid = l + r >> 1;
ll res = 0;
if(tr[u].tag) pushdown(u);
if(L<=mid) res += query(u<<1,l,mid,L,R);
if(mid+1<=R) res += query(u<<1|1,mid+1,r,L,R);
return res;
}
inline void update(ll u,ll l,ll r,ll L,ll R,ll k)
{
if(L<=l&&r<=R)
{
tr[u].tag += k;
tr[u].sum += k*tr[u].len();
}
else
{
if(tr[u].tag) pushdown(u);
ll mid = l + r >> 1;
if(L<=mid) update(u<<1,l,mid,L,R,k);
if(R>=mid+1) update(u<<1|1,mid+1,r,L,R,k);
pushup(u);
}
}
inline ll qRange(ll x,ll y)
{
ll ans = 0;// cout<<"qRange"<<endl;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ll temp = query(1,1,n,id[top[x]],id[x]);
ans += temp;
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return ans + query(1,1,n,id[x],id[y]);
}
inline void upSon(ll u,ll k)
{
update(1,1,n,id[u],id[u]+siz[u]-1,k);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
repd(i,1,n) cin>>val0[i];
repd(i,1,n-1)
{
int u,v;
cin>>u>>v;
g[u].PB(v);g[v].PB(u);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
repd(i,1,m)
{ //cout<<">>>"<<endl;
ll opt,x,y;
cin>>opt;
if(opt==1)
{
cin>>x>>y;
update(1,1,n,id[x],id[x],y);
}
else if(opt==2)
{
cin>>x>>y;
upSon(x,y);
}
else if(opt==3)
{
cin>>x;
cout<<qRange(1,x)<<endl;
}
}
return 0;
}
```
by BeautifulWater @ 2022-03-29 15:36:38