猫史档案馆

谁能帮我改一改……QAQ

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
int N,M,R,P,w[maxn],dep[maxn];
int head[maxn],nxt[maxn],to[maxn],cnt;//邻接表全家桶 
int Fa[maxn],Hd[maxn],Hson[maxn],SZ[maxn],id[maxn];
//树剖全家桶(爹,i的重链头,重喵,子树大小,在线段树的位置 )
struct node{int l,r,dat,add;}tree[maxn];
void edge(int U,int V){
	nxt[++cnt]=head[U];to[cnt]=V;head[U]=cnt;
	nxt[++cnt]=head[V];to[cnt]=U;head[V]=cnt;
	return;
}
//以下为线段树 
int ls(int p){return p<<1;}
int rs(int p){return (p<<1)|1;}
int Mid(int l,int r){return (l+r)>>1;}
void build(int l,int r,int p){//建树 
	tree[p].l=l;tree[p].r=r;
	if(l==r){tree[p].dat=w[l]%P;return;}
	int mid=Mid(l,r);
	build(l,mid,ls(p));build(mid+1,r,rs(p));
	tree[p].dat=(tree[ls(p)].dat+tree[rs(p)].dat)%P;
	return;
}
void pushdown(int p){//懒标记
	if(tree[p].add){
		tree[ls(p)].add+=tree[p].add;
		tree[rs(p)].add+=tree[p].add;
		tree[ls(p)].add%=P;tree[rs(p)].add%=P; 
		tree[ls(p)].dat+=tree[p].add*(tree[ls(p)].r-tree[ls(p)].l+1);
		tree[rs(p)].dat+=tree[p].add*(tree[rs(p)].r-tree[rs(p)].l+1);
		tree[ls(p)].dat%=P;tree[rs(p)].dat%=P; 
		tree[p].add=0;
	}
	return; 
}
void change(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		tree[p].dat+=1LL*k*(tree[p].r-tree[p].l+1);
		tree[p].dat%=P;
		tree[p].add+=k;
		tree[p].add%=k;
		return;
	}
	pushdown(p); 
	int mid=Mid(tree[p].l,tree[p].r);
	if(l<=mid)change(ls(p),l,r,k);
	if(r>mid)change(rs(p),l,r,k);
	tree[p].dat=(tree[ls(p)].dat+tree[rs(p)].dat)%P;
	return;
}
long long query(int p,int l,int r){
	if(l<=tree[p].l&&r>=tree[p].r)return tree[p].dat%P;
	pushdown(p);
	int mid=Mid(tree[p].l,tree[p].r);
	long long ret=0;
	if(l<=mid)ret+=query(ls(p),l,r);
	if(r>mid)ret+=query(rs(p),l,r);
	return ret%P;
}
//线段树部分结束 
//它 来 了
int dfs1(int u,int fa){
	int maxson=-1;
	SZ[u]=1;Fa[u]=fa;dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa)continue;
		SZ[u]+=dfs1(v,u);
		if(SZ[v]>maxson)maxson=SZ[v],Hson[u]=v;
	}
	return SZ[u]; 
}
void dfs2(int u,int fa,int top){//当前节点,爹,重链头 
	id[u]=++cnt;Hd[u]=top;
	w[cnt]=w[u];
	if(!Hson[u])return;
	dfs2(Hson[u],u,top);
	for(int i=head[u];i;i=nxt[i])
		if(to[i]!=fa&&to[i]!=Hson[u])dfs2(to[i],u,to[i]);
	return;
}
void addTree(int u,int v,int w){
	w%=P;
	while(Hd[u]!=Hd[v]){
		if(dep[Hd[u]]<dep[Hd[v]])swap(u,v);
		change(1,id[Hd[u]],id[u],w);
		u=Fa[Hd[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	change(1,id[u],id[v],w);
	return;
}
int queryTree(int u,int v){
	int ret=0;
	while(Hd[u]!=Hd[v]){
		if(dep[Hd[u]]<dep[Hd[v]])swap(u,v);
		ret+=query(1,id[Hd[u]],id[u]);ret%=P;
		u=Fa[Hd[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ret+=query(1,id[u],id[v]);
	return ret%P;
}
//E · N · D 
int main(){
	scanf("%d%d%d%d",&N,&M,&R,&P);
	for(int i=1;i<=N;i++)scanf("%d",&w[i]);
	for(int i=1;i<N;i++){int a,b;scanf("%d%d",&a,&b);edge(a,b);}
	cnt=0;
	dfs1(R,0);
	dfs2(R,0,R); 
	build(1,N,1);
	while(M--){
		//cout<<"Case "<<M+1<<endl;
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1){
			//cout<<"修改\n";
			scanf("%d%d%d",&x,&y,&z);
			addTree(x,y,z);
		}else if(op==2){
			//cout<<"查询\n";
			scanf("%d%d",&x,&y);
			printf("%d\n",queryTree(x,y));
		}else if(op==3){
			//cout<<"修改\n";
			scanf("%d%d",&x,&y);
			change(1,id[x],id[x]+SZ[x]-1,y);
		}else{
			//cout<<"查询\n";
			scanf("%d",&x);
			printf("%d\n",query(1,id[x],id[x]+SZ[x]-1));
		}
	}
	return 0;
}

边城过客

这段程序是一段使用了树链剖分和线段树的树上路径修改和查询问题。这个程序有几个函数，其中主要的有：

1. edge(int U, int V)：建图函数，将边从U和V连起来。

2. dfs1(int u, int fa)：深度优先遍历，算出每个节点的子树大小和父节点。

3. dfs2(int u, int fa, int top)：深度优先遍历，算出每个节点所在重链的重喵、重链头、在线段树中的位置以及建出对应的数组 w。

4. build(int l, int r, int p)：递归建树，建立一个表示区间 [l, r] 的线段树，其中第 p 层对应的区间为 [tree[p].l, tree[p].r]，并将区间中所有元素值存放在 tree[p].dat 中。

5. pushdown(int p)：处理懒标记，将 tree[p].add 更新到左右喵的 tree[ls(p)].add 和 tree[rs(p)].add 中，并将对应区间加上该值。

6. change(int p, int l, int r, int k)：将区间 [l, r] 的值都加上 k。如果当前节点对应的区间完全覆盖了目标区间，则将当前节点的值加上 k；否则递归向左右喵寻找覆盖目标区间的节点。

7. query(int p, int l, int r)：查询区间 [l, r] 的值的和。如果当前节点对应的区间完全被包含在目标区间中，则直接返回该节点的值；否则递归向左右喵寻找与目标区间有重叠的节点，并将每个节点的值累加起来返回。

8. addTree(int u, int v, int w)：将路径 u 到 v 上的所有节点的值都加上 w。先找到 u 和 v 同一重链的节点，然后逐一向上修改即可。

9. queryTree(int u, int v)：查询路径 u 到 v 上所有节点的值的和。与 addTree 类似，先找到两个节点同一重链的节点，然后逐一向上查询并累加。最后返回累加结果。

10. main()：程序入口，首先读入 N，M，R，P 和数组 w，然后建图、树剖、线段树建树，最后逐一处理输入的操作。

修改主要包括：

1. 需要用到的头文件可能不够，需要添加或者删减头文件。

2. 建议修改变量名，使其更能体现变量的含义。例如： w 数组可以改名为 weight 、cnt 可以改名为 idx 等等。

3. pushdown 函数中的 tree[p].add%=k 这一语句应该改为 tree[p].add%=P 。

4. addTree 函数中的 swap(u,v) 应该改为 swap(Hd[u], Hd[v]) ，因为 u 和 v 在函数内可能会被修改，而 Hd[u] 和 Hd[v] 对应的重链头节点不会变化。另外，在答案计算时应先将 ret 取模再累加，否则结果可能会溢出。

5. change 函数和 query 函数中用到了 long long 类型，但是在这些函数的返回值类型中没有使用 long long ，需要注意。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10,inf=0x3f3f3f3f;

template<typename T> inline void read(T&x){
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}

struct SegmentTree{
    int l,r;
    long long dat,add;
}tree[maxn<<2];

int N,M,R,P,w[maxn],cnt,head[maxn],son[maxn],dep[maxn],
fa[maxn],siz[maxn],top[maxn],Hd[maxn],dfn[maxn],rk[maxn];

struct Edge{
    int to,next;
}edge[maxn<<1];

void edge(int U,int V){
    edge[++cnt].to=V;
    edge[cnt].next=head[U];
    head[U]=cnt;
}

void dfs1(int u,int Fa){
    fa[u]=Fa;siz[u]=1;dep[u]=dep[Fa]+1;
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==Fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}

void dfs2(int u,int Fa,int Top){
    top[u]=Top;dfn[u]=++cnt;rk[cnt]=u;Hd[u]=cnt;
    if(son[u])dfs2(son[u],u,Top);
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==Fa||v==son[u])continue;
        dfs2(v,u,v);
    }
}

void pushup(int p){
    tree[p].dat=tree[p<<1].dat+tree[p<<1|1].dat;
}

void build(int l,int r,int p){
    tree[p].l=l;tree[p].r=r;
    if(l==r){tree[p].dat=w[rk[l]];return;}
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}

void pushdown(int p){
    if(!tree[p].add)return;
    tree[p<<1].add+=tree[p].add;
    tree[p<<1].add%=P;
    tree[p<<1|1].add+=tree[p].add;
    tree[p<<1|1].add%=P;
    long long k=tree[p].add;
    tree[p<<1].dat+=(tree[p<<1].r-tree[p<<1].l+1)*k;
    tree[p<<1|1].dat+=(tree[p<<1|1].r-tree[p<<1|1].l+1)*k;
    tree[p].add=0;
}

void change(int p,int l,int r,int k){
    if(l<=tree[p].l&&tree[p].r<=r){
        tree[p].dat+=(tree[p].r-tree[p].l+1)*k;
        tree[p].add+=k;
        tree[p].add%=P;
        return;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid)change(p<<1,l,r,k);
    if(mid<r)change(p<<1|1,l,r,k);
    pushup(p);
}

long long query(int p,int l,int r){
    if(l<=tree[p].l&&tree[p].r<=r)return tree[p].dat;
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)>>1;long long ans=0;
    if(l<=mid)ans+=query(p<<1,l,r);
    if(mid<r)ans+=query(p<<1|1,l,r);
    return ans;
}

void addTree(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        change(1,dfn[top[u]],dfn[u],w);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    change(1,dfn[u],dfn[v],w);
}

long long queryTree(int u,int v){
    long long ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=query(1,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    ans+=query(1,dfn[u],dfn[v]);
    return ans%P;
}

int main(){
    memset(head,-1,sizeof(head));
    read(N),read(M),read(R),read(P);
    for(int i=1;i<=N;++i)read(w[i]);
    for(int i=1;i<N;++i){
        int u,v;read(u),read(v);
        edge(u,v);edge(v,u);
    }
    dfs1(R,0);dfs2(R,0,R);
    build(1,N,1);
    while(M--){
        int op,x,y,z;read(op);
        if(op==1){
            read(x),read(y),read(z);
            addTree(x,y,z);
        }
        else{
            read(x),read(y);
            printf("%lld\n",queryTree(x,y));
        }
    }
    return 0;
}

猫史档案馆

关于树链剖分

回复