做网站需要什么 图片视频,有的网站网速慢,在线编辑图片的网站有哪些,自行车网站模板这里没有水表 树链剖分是一个通过轻重链剖分、dfs序和线段树的使用,在有根树上维护路径和子树信息的有效算法 其预处理时间复杂度为\(O(nlog^2n)\),单次操作时间复杂度为\(O(log^2n)\),常数优秀 主要是防止自己忘记,所以只作简要说明,要学习的可以参考友链里大佬的博客 预处理 …这里没有水表 树链剖分是一个通过轻重链剖分、dfs序和线段树的使用,在有根树上维护路径和子树信息的有效算法 其预处理时间复杂度为\(O(nlog^2n)\),单次操作时间复杂度为\(O(log^2n)\),常数优秀 主要是防止自己忘记,所以只作简要说明,要学习的可以参考友链里大佬的博客 预处理 第一遍dfs 需要处理的数组有\(fa(父亲),son(重儿子),sz(子树大小)和dep(深度)\) ll fa[N],son[N],sz[N],dep[N];
il void dfs1(int u,int f){sz[u]1;fa[u]f;dep[u]dep[f]1;for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vf)continue;dfs1(v,u);sz[u]sz[v];if(!son[u]||sz[v]sz[son[u]])son[u]v;}
} 第二遍dfs 需要处理的数组有\(w(原树节点在线段树节点上的编号),fw(线段树节点在原树节点上的编号),top(所在重链的顶部)\)优先搜索重儿子,因为需要将重链上的节点放在线段树上相邻的位置 ll top[N],w[N],fw[N],cntw;
il void dfs2(int u,int f){top[u](son[fa[u]]u)?top[fa[u]]:u;w[u]cntw;fw[w[u]]u;if(son[u])dfs2(son[u],u);for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vf||vson[u])continue;dfs2(v,u);}
} 其实到这里树链剖分就做完了 build线段树 线段树上节点的值通过\(fw\)数组和原树对应起来(这里以luogu树链剖分模板中的操作为例) #define ls (i1)
#define rs (i1|1)
#define mid ((lr)1)
ll sum[N2],lz[N2];
il void update(int i){sum[i](sum[ls]sum[rs])%mod;}
il void build(ll i,ll l,ll r){if(lr){sum[i]val[fw[l]]%mod;return;}build(ls,l,mid);build(rs,mid1,r);update(i);
} 维护子树信息 以\(x\)为根的子树在线段树上表现出来的区间为\((w[x],w[x]sz[x]-1)\) 修改 il void modify_tree(){RG int xread(),kread();modify(1,1,n,w[x],w[x]sz[x]-1,k);
} 查询 il void query_tree(){RG int xread();printf(%lld\n,query(1,1,n,w[x],w[x]sz[x]-1));
} 维护路径信息 对于一条\(u-v\)的路径,我们根据之前的重链剖分可以将其分成不超过\(log(n)\)条重链, 每条重链分别在线段树上进行维护,这时重链的合并也就成为维护路径信息的一大难点 修改 il void modify_road(){RG int uread(),vread();RG ll kread();while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);modify(1,1,n,w[top[u]],w[u],k);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);modify(1,1,n,w[u],w[v],k);
} 查询 il void query_road(){RG int uread(),vread();RG ll ret0;while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);ret(retquery(1,1,n,w[top[u]],w[u]))%mod;ufa[top[u]];}if(dep[u]dep[v])swap(u,v);printf(%lld\n,(retquery(1,1,n,w[u],w[v]))%mod);
} luogu P3384 【模板】树链剖分 囊括了上面的操作. #includealgorithm
#includeiostream
#includecstdlib
#includeiomanip
#includecstring
#includecomplex
#includevector
#includecstdio
#includestring
#includebitset
#includecmath
#includequeue
#includestack
#includemap
#includeset
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vectorintVI;
typedef long long ll;
typedef double dd;
const dd eps1e-10;
const int N100010;
const int M50010*2;
il ll read(){RG ll data0,w1;RG char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();return data*w;
}ll n,m,r,mod,val[N];
ll head[N],nxt[N1],to[N1],cnt;
il void add(int u,int v){to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}ll fa[N],son[N],sz[N],dep[N];
il void dfs1(int u,int f){sz[u]1;fa[u]f;dep[u]dep[f]1;for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vf)continue;dfs1(v,u);sz[u]sz[v];if(!son[u]||sz[v]sz[son[u]])son[u]v;}
}ll top[N],w[N],fw[N],cntw;
il void dfs2(int u,int f){top[u](son[fa[u]]u)?top[fa[u]]:u;w[u]cntw;fw[w[u]]u;if(son[u])dfs2(son[u],u);for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vf||vson[u])continue;dfs2(v,u);}
}#define ls (i1)
#define rs (i1|1)
#define mid ((lr)1)
ll sum[N2],lz[N2];
il void update(int i){sum[i](sum[ls]sum[rs])%mod;}
il void build(ll i,ll l,ll r){if(lr){sum[i]val[fw[l]]%mod;return;}build(ls,l,mid);build(rs,mid1,r);update(i);
}il void pushdown(ll i,ll l,ll r){if(!lz[i])return;sum[ls](sum[ls]lz[i]*(mid-l1)%mod)%mod;sum[rs](sum[rs]lz[i]*(r-mid)%mod)%mod;lz[ls](lz[ls]lz[i])%mod;lz[rs](lz[rs]lz[i])%mod;lz[i]0;
}il void modify(ll i,ll l,ll r,ll x,ll y,ll k){if(xlry){sum[i](sum[i]k*(r-l1)%mod)%mod;lz[i](lz[i]k)%mod;return;}pushdown(i,l,r);if(xmid)modify(ls,l,mid,x,y,k);if(ymid1)modify(rs,mid1,r,x,y,k);update(i);
}il ll query(ll i,ll l,ll r,ll x,ll y){if(xlry)return sum[i]%mod;pushdown(i,l,r);RG ll s0;if(xmid)squery(ls,l,mid,x,y)%mod;if(ymid1)s(squery(rs,mid1,r,x,y))%mod;return s;
}il void modify_tree(){RG int xread(),kread();modify(1,1,n,w[x],w[x]sz[x]-1,k);
}il void query_tree(){RG int xread();printf(%lld\n,query(1,1,n,w[x],w[x]sz[x]-1));
}il void modify_road(){RG int uread(),vread();RG ll kread();while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);modify(1,1,n,w[top[u]],w[u],k);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);modify(1,1,n,w[u],w[v],k);
}il void query_road(){RG int uread(),vread();RG ll ret0;while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);ret(retquery(1,1,n,w[top[u]],w[u]))%mod;ufa[top[u]];}if(dep[u]dep[v])swap(u,v);printf(%lld\n,(retquery(1,1,n,w[u],w[v]))%mod);
}int main()
{nread();mread();rread();modread();for(RG int i1;in;i)val[i]read()%mod;for(RG int j1,u,v;jn;j){uread();vread();add(u,v);add(v,u);}dfs1(r,0);dfs2(r,0);build(1,1,n);for(RG int i1,opt;im;i){optread();if(opt1)modify_road();if(opt2)query_road();if(opt3)modify_tree();if(opt4)query_tree();}return 0;
} [SDOI2011]染色 询问树上的路径有多少条颜色段,区间修改 记录区间左颜色段,右颜色段,和颜色段数,合并重链时需要留意 #includealgorithm
#includeiostream
#includecstdlib
#includeiomanip
#includecstring
#includecomplex
#includevector
#includecstdio
#includestring
#includebitset
#includecmath
#includequeue
#includestack
#includemap
#includeset
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vectorintVI;
typedef long long ll;
typedef double dd;
const dd eps1e-10;
const int mod1e97;
const int N100100;
const int M50010*2;
il ll read(){RG ll data0,w1;RG char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();return data*w;
}il void file(){freopen(a.in,r,stdin);freopen(a.out,w,stdout);
}int n,m,c[N];char ch;
int head[N],nxt[N1],to[N1],cnt;
il void add(int u,int v){to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}int fa[N],son[N],sz[N],dep[N];
void dfs1(int u){sz[u]1;for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u])continue;fa[v]u;dep[v]dep[u]1;dfs1(v);sz[u]sz[v];if(!son[u]||sz[v]sz[son[u]])son[u]v;}
}int top[N],w[N],fw[N],cntw;
void dfs2(int u,int tp){top[u]tp;w[u]cntw;fw[w[u]]u;if(son[u])dfs2(son[u],tp);for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u]||vson[u])continue;dfs2(v,v);}
}#define ls (i1)
#define rs (i1|1)
#define mid ((lr)1)
int sum[N2],lc[N2],rc[N2],s[N2];
il void update(int i){sum[i]sum[ls]sum[rs]-(rc[ls]lc[rs]);lc[i]lc[ls];rc[i]rc[rs];
}
void build(int i,int l,int r){if(lr){sum[i]1;lc[i]rc[i]c[fw[l]];return;}build(ls,l,mid);build(rs,mid1,r);update(i);
}
il void pushdown(int i){if(!s[i])return;sum[ls]sum[rs]1;s[ls]s[rs]lc[ls]rc[ls]lc[rs]rc[rs]s[i];s[i]0;
}void modify(int i,int l,int r,int x,int y,int w){if(xlry){sum[i]1;s[i]lc[i]rc[i]w;return;}pushdown(i);if(xmid)modify(ls,l,mid,x,y,w);if(ymid)modify(rs,mid1,r,x,y,w);update(i);
}int query(int i,int l,int r,int x,int y,int L,int R){if(xlry){Llc[i];Rrc[i];return sum[i];}pushdown(i);if(xmidymid)return query(ls,l,mid,x,y,L,R);if(xmidymid)return query(rs,mid1,r,x,y,L,R);RG int lr0,rl0,s0;squery(ls,l,mid,x,y,L,lr)query(rs,mid1,r,x,y,rl,R);if(lrrllr)s--;return s;
}il void modify_road(){RG int uread(),vread(),kread();while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);modify(1,1,n,w[top[u]],w[u],k);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);modify(1,1,n,w[u],w[v],k);
}il void query_road(){RG int uread(),vread(),tu-1,tv-1,l0,r0,sum0,ret;while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v),swap(tu,tv);retquery(1,1,n,w[top[u]],w[u],l,r);sumret;if(rtu)sum--;tul;ufa[top[u]];}if(dep[u]dep[v])swap(u,v),swap(tu,tv);retquery(1,1,n,w[u],w[v],l,r);sumret;if(ltu)sum--;if(rtv)sum--;printf(%d\n,sum);
}int main()
{nread();mread();for(RG int i1;in;i)c[i]read();for(RG int i1,u,v;in;i){uread();vread();add(u,v);add(v,u);}dfs1(1);dfs2(1,1);build(1,1,n);for(RG int i1;im;i){ch0;while(ch!Cch!Q)chgetchar();if(chC)modify_road();else query_road();}return 0;
} [NOI2015]软件包管理器 其实就是弱化版的模板。 #includealgorithm
#includeiostream
#includecstdlib
#includeiomanip
#includecstring
#includecomplex
#includevector
#includecstdio
#includestring
#includebitset
#includecmath
#includequeue
#includestack
#includemap
#includeset
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vectorintVI;
typedef long long ll;
typedef double dd;
const dd eps1e-10;
const int mod1e97;
const int N100010;
const int M50010*2;
il ll read(){RG ll data0,w1;RG char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();return data*w;
}il void file(){freopen(a.in,r,stdin);freopen(a.out,w,stdout);
}int n,q;char ch[10];
int head[N],nxt[N1],to[N1],cnt;
il void add(int u,int v){to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}int sz[N],fa[N],dep[N],son[N];
void dfs1(int u){sz[u]1;for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u])continue;fa[v]u;dep[v]dep[u]1;dfs1(v);sz[u]sz[v];if(!son[u]||sz[v]sz[son[u]])son[u]v;}
}int top[N],w[N],fw[N],cntw;
void dfs2(int u,int tp){top[u]tp;w[u]cntw;fw[w[u]]u;if(son[u])dfs2(son[u],tp);for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u]||vson[u])continue;dfs2(v,v);}
}#define ls (i1)
#define rs (i1|1)
#define mid ((lr)1)
int sum[2][N2],lz[N2];
//初始时lz-1
il void update(int i){sum[0][i]sum[0][ls]sum[0][rs];sum[1][i]sum[1][ls]sum[1][rs];
}
il void pushdown(int i,int l,int r){if(lz[i]-1)return;lz[ls]lz[rs]lz[i];sum[lz[ls]^1][ls]0;sum[lz[ls]][ls]mid-l1;sum[lz[rs]^1][rs]0;sum[lz[rs]][rs]r-mid;lz[i]-1;
}
il void build(int i,int l,int r){lz[i]-1;if(lr){sum[0][i]1;sum[1][i]0;return;}build(ls,l,mid);build(rs,mid1,r);update(i);
}il void modify(int i,int l,int r,int x,int y,int k){if(xlry){lz[i]k;sum[k][i]r-l1;sum[k^1][i]0;return;}pushdown(i,l,r);if(xmid)modify(ls,l,mid,x,y,k);if(ymid)modify(rs,mid1,r,x,y,k);update(i);
}il int query(int i,int l,int r,int x,int y,int k){if(xlry)return sum[k][i];pushdown(i,l,r);RG int s0;if(xmid)squery(ls,l,mid,x,y,k);if(ymid)squery(rs,mid1,r,x,y,k);return s;
}il void modify_tree(int u,int k){modify(1,1,n,w[u],w[u]sz[u]-1,k);
}
il void query_tree(int u,int k){printf(%d\n,query(1,1,n,w[u],w[u]sz[u]-1,k));
}il void modify_road(int u,int v,int k){while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);modify(1,1,n,w[top[u]],w[u],k);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);modify(1,1,n,w[u],w[v],k);
}il void query_road(int u,int v,int k){RG int s0;while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);squery(1,1,n,w[top[u]],w[u],k);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);printf(%d\n,squery(1,1,n,w[u],w[v],k));
}int main()
{nread();for(RG int i2;in;i){fa[i]read()1;add(i,fa[i]);add(fa[i],i);}dfs1(1);dfs2(1,1);build(1,1,n);qread();for(RG int i1,x;iq;i){scanf(%s,ch1);xread()1;if(ch[1]i)query_road(1,x,0),modify_road(1,x,1);else query_tree(x,1),modify_tree(x,0);}return 0;
} [JLOI2014]松鼠的新家 本来是树上差分来着...被我拿树剖来练手了。 #includealgorithm
#includeiostream
#includecstdlib
#includeiomanip
#includecstring
#includecomplex
#includevector
#includecstdio
#includestring
#includebitset
#includecmath
#includequeue
#includestack
#includemap
#includeset
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vectorintVI;
typedef long long ll;
typedef double dd;
const dd eps1e-10;
const int mod1e97;
const int N300010;
const int M50010*2;
il ll read(){RG ll data0,w1;RG char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();return data*w;
}il void file(){freopen(a.in,r,stdin);freopen(a.out,w,stdout);
}int n,a[N];
int head[N],nxt[N1],to[N1],cnt;
il void add(int u,int v){to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}int sz[N],fa[N],son[N],dep[N];
void dfs1(int u){sz[u]1;for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u])continue;dep[v]dep[u]1;fa[v]u;dfs1(v);sz[u]sz[v];if(!son[u]||sz[son[u]]sz[v])son[u]v;}
}int top[N],w[N],fw[N],cntw;
void dfs2(int u,int tp){top[u]tp;w[u]cntw;fw[w[u]]u;if(son[u])dfs2(son[u],tp);for(RG int ihead[u];i;inxt[i]){RG int vto[i];if(vfa[u]||vson[u])continue;dfs2(v,v);}
}#define ls (i1)
#define rs (i1|1)
#define mid ((lr)1)
ll sum[N2],lz[N2];
il void update(int i){sum[i]sum[ls]sum[rs];}
il void pushdown(int i,int l,int r){if(!lz[i])return;sum[ls]lz[i]*(mid-l1);sum[rs]lz[i]*(r-mid);lz[ls]lz[i];lz[rs]lz[i];lz[i]0;
}il void modify(int i,int l,int r,int x,int y,int k){if(xlry){lz[i]k;sum[i]k*(r-l1);return;}pushdown(i,l,r);if(xmid)modify(ls,l,mid,x,y,k);if(ymid)modify(rs,mid1,r,x,y,k);update(i);
}il ll query(int i,int l,int r,int x,int y){if(xlry)return sum[i];pushdown(i,l,r);RG ll s0;if(xmid)squery(ls,l,mid,x,y);if(ymid)squery(rs,mid1,r,x,y);return s;
}il void modify_road(int u,int v){while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);modify(1,1,n,w[top[u]],w[u],1);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);modify(1,1,n,w[u],w[v],1);
}int main()
{nread();for(RG int i1;in;i)a[i]read();for(RG int i1,u,v;in;i){uread();vread();add(u,v);add(v,u);}dfs1(1);dfs2(1,1);for(RG int i2;in;i){modify_road(a[i-1],a[i]);modify(1,1,n,w[a[i]],w[a[i]],-1);}for(RG int i1;in;i)printf(%lld\n,query(1,1,n,w[i],w[i]));return 0;
} 未完待续......(其实是我写的题太少了) 转载于:https://www.cnblogs.com/cjfdf/p/8470788.html
