SS241128D. 旅行 (tour)
题意
给你一棵 \(n\) 个点的以 \(1\) 为根的树，每个结点有点权 \(a_i\)。有 \(m\) 次操作。操作分 \(4\) 种。
- 查询 \(u\) 的点权。
- 令 \(u,v\) 路径上所有点 \(p\) 的点权 \(a_p \gets ka_p + b\)。
- 令 \(u\) 的子树所有点 \(p\) 的点权 \(a_p \gets ka_p + b\)。
- 令距离 \(u\) 不超过 \(d\) 的所有点 \(p\) 的点权 \(a_p \gets ka_p + b\)。
其中 \(d \le 10, n,m \le 10^5\)。
思路
因为有链和子树操作，容易想到重剖。
题解说有这两个操作，限定了只能在 dfs 序上做。
发现 \(d \le 10\)，考虑比较暴力地维护操作 \(4\)。
如果 \(k=1\)，那么操作就具有交换律和结合律，可以分别处理链剖分和邻域操作，邻域操作可以对每个点打 \(tag_{0 \sim 10}\) 表示给 \(u\) 的子树里距离 \(u\) 为 \(0 \sim 10\) 的结点的标记。修改的时候就修改 \(u\) 和它的 \(d\) 层祖先，注意容斥一下，查询的时候就访问它的 \(d\) 层祖先。因为操作满足交换律，使用标记永久化以保证时间复杂度。
时间复杂度 \(O(m (\log^2 n + d))\)，写得丑可能会变成 \(d^2\)。
但是这里的操作虽然满足结合率，不满足交换律。不标记永久化时间复杂度会退化成单次 \(O(n)\)。
我们必须要在 dfs 序上维护这些操作。考虑刚刚的标记其实给一棵子树对应的一段连续的 dfs 序打上对应深度的标记。我们可以在线段树里打这些标记。如何下放标记？直接给两个儿子下放，和线段树下放标记差不多。
时间复杂度 \(O(m(\log^2 nd+\log nd^2))\)。常数小，\(1s\) 内可以跑完。
code
感觉不是很好写啊。
其实还行，参考了 std 的写法。发现我的树剖马蜂属实诡异。原来别人的树剖和我的写法有一些不同，我的树剖写了很多废的东西啊，这就去改板子。
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace humorous {
#define isdigit(x) (x>='0'&&x<='9')
#define gc getchar_unlocked
#define pc putchar_unlocked
template <typename T>
void read(T &x) {
x=0;
char ch=gc();
for(;!isdigit(ch);ch=gc());
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
}
template <typename T>
void write(T x,char ch) {
static int st[40];
int top=0;
do {
st[top++]=x%10;
x/=10;
}while(x);
while(top) pc(st[--top]^48);
pc(ch);
}
constexpr int N=1e5+7,mod=998244353,B=10;
int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
void _add(int &a,int b) { a=add(a,b); }
int mul(int a,int b) { return 1ll*a*b%mod; }
void _mul(int &a,int b) { a=mul(a,b); }
int sub,n,m;
int u,v,a[N],op;
int k,b,d;
vector<int> to[N];
int fa[N],dep[N];
int cnt;
int dfn[N],idfn[N],top[N],eddfn[N];
int siz[N],gson[N];
void dfs(int u,int f) {
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
for(int v:to[u]) if(v^f) {
dfs(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[gson[u]]) gson[u]=v;
}
}
void dfs(int u) {
dfn[u]=++cnt;
idfn[cnt]=u;
if(gson[u]) top[gson[u]]=top[u], dfs(gson[u]);
for(int v:to[u]) if((v^fa[u]) && (v^gson[u])) top[v]=v, dfs(v);
eddfn[u]=cnt;
}
struct pii{
int x,y;
pii operator * (pii b) const { return {mul(x,b.x), add(mul(y,b.x),b.y)}; }
};
pii tr[N<<2][12];
int mindep[N<<2];
void build(int u,int l,int r) {
rep(i,0,11) tr[u][i].x=1;
if(l==r) return mindep[u]=dep[idfn[l]], tr[u][0]={0,a[idfn[l]]}, void(0);
int mid=(l+r)>>1;
build(u<<1,l,mid), build(u<<1|1,mid+1,r);
mindep[u]=min(mindep[u<<1],mindep[u<<1|1]);
}
void init() {
dfs(1,0);
top[1]=1;
dfs(1);
build(1,1,n);
}
void f(int u,pii tg,int dep) {
if(dep>=mindep[u]) tr[u][dep-mindep[u]]=tr[u][dep-mindep[u]]*tg;
}
void pushdown(int u) {
rep(i,0,B) {
if(tr[u][i].x!=1 || tr[u][i].y) {
f(u<<1,tr[u][i],mindep[u]+i);
f(u<<1|1,tr[u][i],mindep[u]+i);
tr[u][i]={1,0};
}
}
if(tr[u][11].x!=1 || tr[u][11].y) {
int tmp=max(0,mindep[u]+11-mindep[u<<1]);
rep(i,tmp,11) tr[u<<1][i]=tr[u<<1][i]*tr[u][11];
tmp=max(0,mindep[u]+11-mindep[u<<1|1]);
rep(i,tmp,11) tr[u<<1|1][i]=tr[u<<1|1][i]*tr[u][11];
tr[u][11]={1,0};
}
}
int query(int u,int l,int r,int x) {
if(l==r) return tr[u][0].y;
int mid=(l+r)>>1;
pushdown(u);
if(x<=mid) return query(u<<1,l,mid,x);
return query(u<<1|1,mid+1,r,x);
}
void _update(int u,int l,int r,int L,int R,pii x) {
if(l>=L && r<=R) {
rep(i,0,11) tr[u][i]=tr[u][i]*x;
return;
}
int mid=(l+r)>>1;
pushdown(u);
if(L<=mid) _update(u<<1,l,mid,L,R,x);
if(mid+1<=R) _update(u<<1|1,mid+1,r,L,R,x);
}
void _update2(int u,int l,int r,int L,int R,int dep,pii x) {
if(mindep[u]>dep) return;
if(l>=L&&r<=R) return tr[u][dep-mindep[u]]=tr[u][dep-mindep[u]]*x, void(0);
int mid=(l+r)>>1;
pushdown(u);
if(L<=mid) _update2(u<<1,l,mid,L,R,dep,x);
if(mid+1<=R) _update2(u<<1|1,mid+1,r,L,R,dep,x);
}
void update2(int u,int v,pii x) {
while(top[u]^top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
_update(1,1,n,dfn[top[u]],dfn[u],x), u=fa[top[u]];
}
if(dfn[u]>dfn[v]) swap(u,v);
_update(1,1,n,dfn[u],dfn[v],x);
}
void update3(int u,pii x) { _update(1,1,n,dfn[u],eddfn[u],x); }
void update4(int u,int d,pii x) {
while(~d && u) {
if(d && fa[u]) {
_update2(1,1,n,dfn[u],eddfn[u],dep[u]+d,x);
_update2(1,1,n,dfn[u],eddfn[u],dep[u]+d-1,x);
}else {
rep(i,0,d) _update2(1,1,n,dfn[u],eddfn[u],dep[u]+i,x);
}
u=fa[u], --d;
}
}
void main() {
read(sub),read(n),read(m);
rep(i,1,n-1) {
read(u),read(v);
to[u].push_back(v), to[v].push_back(u);
}
rep(i,1,n) read(a[i]);
init();
rep(i,1,m) {
read(op), read(u);
if(op==1) write(query(1,1,n,dfn[u]),'\n');
else if(op==2) read(v),read(k),read(b), update2(u,v,{k,b});
else if(op==3) read(k),read(b), update3(u,{k,b});
else read(d),read(k),read(b), update4(u,d,{k,b});
}
}
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
#endif
humorous :: main();
}