NOIP 前挂了树剖求条,玄关

P3384 【模板】重链剖分/树链剖分

WxjzKK @ 2023-11-17 20:54:51

要考 $NOIP$ 了,急,玄关。 开了 `long long` 并没有什么卵用。 ```cpp //【模板】树链剖分 #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; inline void read(int &n){ int s=0,t=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') t=-1; c=getchar(); } while(c>='0'&&c<='9'){ s=(s<<3)+(s<<1)+(c^48);c=getchar(); } n=s*t; } inline void put(int n){ if(n<0){ putchar('-');n=-n; } if(n<10){ putchar(n+48);return; } put(n/10); putchar(n%10+48); } struct node{ int v,nxt; }e[MAXN<<1]; struct sgt{ int l,r,sum,tag; }t[MAXN<<1]; int n,p,root,tot,cnt,tal,a[MAXN],b[MAXN],head[MAXN],dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN],id[MAXN],top[MAXN]; inline void add(int u,int v){ ++tot; e[tot].v=v; e[tot].nxt=head[u]; head[u]=tot; } inline void dfs1(int u,int f){ fa[u]=f;dep[u]=dep[f]+1;siz[u]=1; for(register int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if(v!=f){ dfs1(v,u);siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } } inline void dfs2(int u,int ltop){ id[u]=++cnt;b[cnt]=a[u];top[u]=ltop; if(son[u]) dfs2(son[u],ltop); for(register int i=head[u];i;i=e[i].nxt){ int v=e[i].v; if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } inline void pushup(int rt){ t[rt].sum=(t[t[rt].l].sum+t[t[rt].r].sum)%p; } inline void pushdown(int rt,int l,int r){ if(t[rt].tag){ int mid=(l+r)>>1; t[t[rt].l].sum=(t[t[rt].l].sum+(mid-l+1)*t[rt].tag)%p; t[t[rt].r].sum=(t[t[rt].r].sum+(r-mid)*t[rt].tag)%p; t[t[rt].l].tag=(t[t[rt].l].tag+t[rt].tag)%p; t[t[rt].r].tag=(t[t[rt].r].tag+t[rt].tag)%p; t[rt].tag=0; } } inline void build(int &rt,int l,int r){ if(!rt) rt=++tot; if(l==r){ t[tot].sum=b[l]%p;return; } int mid=(l+r)>>1; build(t[rt].l,l,mid);build(t[rt].r,mid+1,r); pushup(rt); } inline void update(int rt,int l,int r,int left,int right,int x){ if(l>=left&&r<=right){ t[rt].sum=(t[rt].sum+(r-l+1)*x)%p;t[rt].tag=(t[rt].tag+x)%p;return; } pushdown(rt,l,r); int mid=(l+r)>>1; if(left<=mid) update(t[rt].l,l,mid,left,right,x); if(right>mid) update(t[rt].r,mid+1,r,left,right,x); pushup(rt); } inline int query(int rt,int l,int r,int left,int right){ if(l>=left&&r<=right) return t[rt].sum; pushdown(rt,l,r); int mid=(l+r)>>1,ans=0; if(left<=mid) ans=(ans+query(t[rt].l,l,mid,left,right))%p; if(right>mid) ans=(ans+query(t[rt].r,mid+1,r,left,right))%p; return ans; } inline void range(int x,int y,int z){ while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]) swap(x,y); update(root,1,n,id[top[y]],id[y],z);y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); update(root,1,n,id[x],id[y],z); } inline int getsum(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]]) swap(x,y); ans=(ans+query(root,1,n,id[top[y]],id[y]))%p;y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); ans=(ans+query(root,1,n,id[x],id[y]))%p; return ans; } int main(){ int m,r,opt,x,y,z; read(n);read(m);read(r);read(p); for(register int i=1;i<=n;++i) read(a[i]); for(register int i=1;i<n;++i){ read(x);read(y);add(x,y);add(y,x); } dfs1(r,0);dfs2(r,r);build(root,1,n); for(register int i=1;i<=m;++i){ read(opt);read(x); if(opt==1){ read(y);read(z);range(x,y,z%p); } else if(opt==2){ read(y);put(getsum(x,y));putchar('\n'); } else if(opt==3){ read(z);update(root,1,n,id[x],id[x]+siz[x]-1,z%p); } else{ put(query(root,1,n,id[x],id[x]+siz[x]-1));putchar('\n'); } } return 0; } ```

by _radio_ @ 2023-11-17 21:03:52

《线段树空间只<<1》,<<2就过了


by WxjzKK @ 2023-11-17 21:18:59

@swyn 谢谢,已关


|