2020-2021:teams:legal_string:jxm2001:重链剖分
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:重链剖分 [2020/05/24 18:06] jxm2001 |
2020-2021:teams:legal_string:jxm2001:重链剖分 [2021/08/04 20:37] (当前版本) jxm2001 [代码模板] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| 一种动态维护树上路径、子树信息的算法，单次操作时间复杂度 $O\left(\log^2 n\right)$ | 一种动态维护树上路径、子树信息的算法，单次操作时间复杂度 $O\left(\log^2 n\right)$ | ||
| - | ===== 算法思想 ==== | + | ===== 算法思想 ===== |
| 重链剖分的关键是把树上修改问题转化为区间修改问题 | 重链剖分的关键是把树上修改问题转化为区间修改问题 | ||
| 行 47: | 行 47: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| int mod; | int mod; | ||
| 行 144: | 行 115: | ||
| head[u]=m; | head[u]=m; | ||
| } | } | ||
| - | int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t; | + | int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],dfs_t; |
| - | int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN]; | + | int h_son[MAXN],mson[MAXN],p[MAXN],dfw[MAXN]; |
| void dfs_1(int u,int fa,int depth){ | void dfs_1(int u,int fa,int depth){ | ||
| - | sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0; | + | sz[u]=1,f[u]=fa,d[u]=depth,mson[u]=0; |
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| 行 161: | 行 132: | ||
| } | } | ||
| void dfs_2(int u,int top){ | void dfs_2(int u,int top){ | ||
| - | dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u]; | + | dfn[u]=++dfs_t,p[u]=top; |
| + | dfw[dfs_t]=w[u]; | ||
| if(mson[u]) | if(mson[u]) | ||
| dfs_2(h_son[u],top); | dfs_2(h_son[u],top); | ||
| 行 171: | 行 143: | ||
| } | } | ||
| } | } | ||
| - | LL query_son(int u){return tree.query(1,dfs_id[u],dfs_id[u]+sz[u]-1);} | + | int query_path(int u,int v){ |
| - | void update_son(int u,int w){tree.update(1,dfs_id[u],dfs_id[u]+sz[u]-1,w);} | + | |
| - | LL query_path(int u,int v){ | + | |
| LL ans=0; | LL ans=0; | ||
| while(p[u]!=p[v]){ | while(p[u]!=p[v]){ | ||
| if(d[p[u]]<d[p[v]]) | if(d[p[u]]<d[p[v]]) | ||
| swap(u,v); | swap(u,v); | ||
| - | ans=(ans+tree.query(1,dfs_id[p[u]],dfs_id[u]))%mod; | + | ans=(ans+tree.query(1,dfn[p[u]],dfn[u]))%mod; |
| u=f[p[u]]; | u=f[p[u]]; | ||
| } | } | ||
| if(d[u]>d[v]) | if(d[u]>d[v]) | ||
| swap(u,v); | swap(u,v); | ||
| - | ans=(ans+tree.query(1,dfs_id[u],dfs_id[v]))%mod; | + | ans=(ans+tree.query(1,dfn[u],dfn[v]))%mod; |
| return ans; | return ans; | ||
| } | } | ||
| 行 190: | 行 160: | ||
| if(d[p[u]]<d[p[v]]) | if(d[p[u]]<d[p[v]]) | ||
| swap(u,v); | swap(u,v); | ||
| - | tree.update(1,dfs_id[p[u]],dfs_id[u],w); | + | tree.update(1,dfn[p[u]],dfn[u],w); |
| u=f[p[u]]; | u=f[p[u]]; | ||
| } | } | ||
| if(d[u]>d[v]) | if(d[u]>d[v]) | ||
| swap(u,v); | swap(u,v); | ||
| - | tree.update(1,dfs_id[u],dfs_id[v],w); | + | tree.update(1,dfn[u],dfn[v],w); |
| } | } | ||
| + | int query_son(int u){return tree.query(1,dfn[u],dfn[u]+sz[u]-1);} | ||
| + | void update_son(int u,int w){tree.update(1,dfn[u],dfn[u]+sz[u]-1,w);} | ||
| int main() | int main() | ||
| { | { | ||
| 行 247: | 行 219: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| #define lowbit(x) ((x)&(-x)) | #define lowbit(x) ((x)&(-x)) | ||
| 行 406: | 行 350: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <cstdio> | ||
| - | #include <algorithm> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=1e5+5; | const int MAXN=1e5+5; | ||
| int lef_color,rig_color; | int lef_color,rig_color; | ||
2020-2021/teams/legal_string/jxm2001/重链剖分.1590314793.txt.gz · 最后更改: 2020/05/24 18:06 由 jxm2001
