蒟蒻重链剖分TLE两个点，长链剖分跑了854ms，求助为什么
- 板块P2590 [ZJOI2008] 树的统计
- 楼主zuishuai
- 当前回复8
- 已保存回复8
- 发布时间2021/11/18 14:26
- 上次更新2023/11/4 00:15:39
查看原帖
被骇客银狼阻止的越权访问保存失败
蒟蒻重链剖分TLE两个点，长链剖分跑了854ms，求助为什么
重链剖分：
#include<bits/stdc++.h>
#define N 400005
#define M 400005
//#define int long long
#define ls (w<<1)
#define rs ((w<<1)|1)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^48),
ch=getchar();
return x*f;
}
inline void write(int x){
int tmp=x<0?-x:x,cnt=0;char f[70];
if(!x)
putchar('0');
if(x<0)
putchar('-');
while(tmp){
f[cnt++]=tmp%10+'0';
tmp/=10;
}
while(cnt)
putchar(f[--cnt]);
putchar('\n');
}
int head[N],nxt[M],to[M],t,u,v;
inline void add(){
nxt[++t]=head[u],head[u]=t,to[t]=v,
nxt[++t]=head[v],head[v]=t,to[t]=u;
}
int n,m,V[N],b[N<<2],d[N],id,dfn[N];
int son[N],top[N],f[N],sz[N],dep[N],maxn[N<<2];
inline void push_up(int w){
b[w]=b[ls]+b[rs],
maxn[w]=max(maxn[ls],maxn[rs]);
}
inline void build(int w,int l,int r){
if(l==r){
maxn[w]=b[w]=d[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),
build(rs,mid+1,r),
push_up(w);
}
inline void dfs1(int x,int fa){
dep[x]=dep[fa]+1,
sz[x]=1,
f[x]=fa;
int maxson=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa)
dfs1(to[i],x),
sz[i]+=sz[to[i]],
maxson=sz[to[i]]>sz[maxson]?to[i]:maxson;
son[x]=maxson;
}
inline void dfs2(int x,int tp){
dfn[x]=++id,
d[id]=V[x],
top[x]=tp;
if(son[x])
dfs2(son[x],tp);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=f[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
inline void update(int w,int l,int r,int x,int k){
if(l==r){
maxn[w]=b[w]=k;
return;
}
int mid=(l+r)>>1;
if(x<=mid)
update(ls,l,mid,x,k);
else
update(rs,mid+1,r,x,k);
push_up(w);
}
inline int querymax(int w,int l,int r,int L,int R){
if(L<=l&&R>=r)
return maxn[w];
int mid=(l+r)>>1,res=-1e9;
if(L<=mid)
res=querymax(ls,l,mid,L,R);
if(R>mid)
res=max(res,querymax(rs,mid+1,r,L,R));
return res;
}
inline int querysum(int w,int l,int r,int L,int R){
// if(L>R || L<1 || R>n) return 0;
if(L<=l&&R>=r)
return b[w];
int mid=((l+r)>>1),res=0;
if(L<=mid)
res=querysum(ls,l,mid,L,R);
if(R>mid)
res+=querysum(rs,mid+1,r,L,R);
return res;
}
inline int requerysum(int l,int r){
int res=0;
while(top[l]!=top[r]){
if(dep[top[l]]<dep[top[r]])
swap(l,r);
res+=querysum(1,1,n,dfn[top[l]],dfn[l]),
l=f[top[l]];
}
if(dep[l]>dep[r])
swap(l,r);
return res+querysum(1,1,n,dfn[l],dfn[r]);
}
inline int requerymax(int l,int r){
int res=-1e9;
while(top[l]!=top[r]){
if(dep[top[l]]<dep[top[r]])
swap(l,r);
res=max(res,querymax(1,1,n,dfn[top[l]],dfn[l])),
l=f[top[l]];
}
if(dep[l]>dep[r])
swap(l,r);
return max(res,querymax(1,1,n,dfn[l],dfn[r]));
}
char s[100];
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(int i=1;i<n;++i)
u=read(),v=read(),
add();
for(int i=1;i<=n;++i)
V[i]=read();
sz[0]=-1e9,
dfs1(1,0),
dfs2(1,1),
build(1,1,n),
m=read();
while(m--){
scanf("%s",s),
u=read(),v=read();
if(*s=='C')
update(1,1,n,dfn[u],v);
else if(*s=='Q'&&s[1]=='M')
write(requerymax(u,v));
else
write(requerysum(u,v));
}
return 0;
}
长链剖分：
#include<bits/stdc++.h>
#define N 400005
#define M 400005
//#define int long long
#define ls (w<<1)
#define rs ((w<<1)|1)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^48),
ch=getchar();
return x*f;
}
inline void write(int x){
int tmp=x<0?-x:x,cnt=0;char f[70];
if(!x)
putchar('0');
if(x<0)
putchar('-');
while(tmp){
f[cnt++]=tmp%10+'0';
tmp/=10;
}
while(cnt)
putchar(f[--cnt]);
putchar('\n');
}
int head[N],nxt[M],to[M],t,u,v;
inline void add(){
nxt[++t]=head[u],head[u]=t,to[t]=v,
nxt[++t]=head[v],head[v]=t,to[t]=u;
}
int n,m,V[N],b[N<<2],d[N],id,dfn[N];
int son[N],top[N],f[N],dep[N],sz[N],maxn[N<<2];
inline void push_up(int w){
b[w]=b[ls]+b[rs],
maxn[w]=max(maxn[ls],maxn[rs]);
}
inline void build(int w,int l,int r){
if(l==r){
maxn[w]=b[w]=d[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),
build(rs,mid+1,r),
push_up(w);
}
inline void dfs1(int x,int fa){
sz[x]=dep[x]=dep[fa]+1,
f[x]=fa;
int maxson=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa){
dfs1(to[i],x);
if(sz[to[i]]>sz[x])
maxson=to[i],
sz[x]=sz[to[i]];
}
son[x]=maxson;
}
inline void dfs2(int x,int tp){
dfn[x]=++id,
d[id]=V[x],
top[x]=tp;
if(son[x])
dfs2(son[x],tp);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=f[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
inline void update(int w,int l,int r,int x,int k){
if(l==r){
maxn[w]=b[w]=k;
return;
}
int mid=(l+r)>>1;
if(x<=mid)
update(ls,l,mid,x,k);
else
update(rs,mid+1,r,x,k);
push_up(w);
}
inline int querymax(int w,int l,int r,int L,int R){
if(L<=l&&R>=r)
return maxn[w];
int mid=(l+r)>>1,res=-1e9;
if(L<=mid)
res=querymax(ls,l,mid,L,R);
if(R>mid)
res=max(res,querymax(rs,mid+1,r,L,R));
return res;
}
inline int querysum(int w,int l,int r,int L,int R){
// if(L>R || L<1 || R>n) return 0;
if(L<=l&&R>=r)
return b[w];
int mid=((l+r)>>1),res=0;
if(L<=mid)
res=querysum(ls,l,mid,L,R);
if(R>mid)
res+=querysum(rs,mid+1,r,L,R);
return res;
}
inline int requerysum(int l,int r){
int res=0;
while(top[l]!=top[r]){
if(dep[top[l]]<dep[top[r]])
swap(l,r);
res+=querysum(1,1,n,dfn[top[l]],dfn[l]),
l=f[top[l]];
}
if(dep[l]>dep[r])
swap(l,r);
return res+querysum(1,1,n,dfn[l],dfn[r]);
}
inline int requerymax(int l,int r){
int res=-1e9;
while(top[l]!=top[r]){
if(dep[top[l]]<dep[top[r]])
swap(l,r);
res=max(res,querymax(1,1,n,dfn[top[l]],dfn[l])),
l=f[top[l]];
}
if(dep[l]>dep[r])
swap(l,r);
return max(res,querymax(1,1,n,dfn[l],dfn[r]));
}
char s[100];
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(int i=1;i<n;++i)
u=read(),v=read(),
add();
for(int i=1;i<=n;++i)
V[i]=read();
sz[0]=-1e9,
dfs1(1,0),
dfs2(1,1),
build(1,1,n),
m=read();
while(m--){
scanf("%s",s),
u=read(),v=read();
if(*s=='C')
update(1,1,n,dfn[u],v);
else if(*s=='Q'&&s[1]=='M')
write(requerymax(u,v));
else
write(requerysum(u,v));
}
return 0;
}
不一样的地方：
inline void dfs1(int x,int fa){
dep[x]=dep[fa]+1,
sz[x]=1,
f[x]=fa;
int maxson=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa)
dfs1(to[i],x),
sz[i]+=sz[to[i]],
maxson=sz[to[i]]>sz[maxson]?to[i]:maxson;
son[x]=maxson;
}
inline void dfs1(int x,int fa){
sz[x]=dep[x]=dep[fa]+1,
f[x]=fa;
int maxson=0;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa){
dfs1(to[i],x);
if(sz[to[i]]>sz[x])
maxson=to[i],
sz[x]=sz[to[i]];
}
son[x]=maxson;
}
调了很久了，是蒟蒻常数太大了吗QWQ
加载中...