codechef Dynamic GCD

题意:给出一棵点权树，每次或者询问两点之间路径上所有点点权的gcd，或者把两点之间路径上所有点的点权同时加上一个数

考虑链上的做法，得到了链上做法之后在树上就只需要树链剖分就行了。

由更相减损术得，序列a₁,a₂,..,a_n的gcd等于序列a₁,a₂-a₁,a₃-a₂,...,a_n-a_n-1的gcd。

那么对于链上我们就维护一阶差分的区间gcd，以及原数列的增量就好。

前一个信息我们用线段树维护，后一个信息我们用bit维护。

在树上的推广:用线段树维护每条重链的区间gcd，用bit维护每个点的增量。

Portal

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define lch x->l,l,mid
#define rch x->r,mid+1,r
#define rep(i,a,b) for(int i=a;i<b;++i)

inline int gcd(int a,int b){
	for(;b;swap(a,b),b%=a);
	return a>0?a:-a; 
}

const int MAXN=50005;

typedef struct node*star;

struct node{
	int x;
	star l,r,p;
	inline void update(){
		x=gcd(l->x,r->x);
	}
}pool[MAXN<<1];
star tail=pool;

int a[MAXN],b[MAXN];

star pos[MAXN];

void build(star&x,int l,int r){
	x=tail++;
	if(l==r){
		x->x=b[l];
		pos[l]=x;
		return;
	}
	int mid=(l+r)>>1;
	build(lch),build(rch);
	x->l->p=x->r->p=x;
	x->update();
}

int query(star x,int l,int r,int ll,int rr){
	if(ll>rr)return 0;
	if(l==ll&&r==rr)return x->x;
	int mid=(l+r)>>1;
	if(rr<=mid)return query(lch,ll,rr);
	if(ll>mid) return query(rch,ll,rr);
	return gcd(query(lch,ll,mid),query(rch,mid+1,rr));
}

int n;

struct edge{
	int t,n;
	edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int ch[MAXN],p[MAXN];

int dep[MAXN],siz[MAXN];

void dfs(int x){
	siz[x]=1;
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			p[y]=x,dep[y]=dep[x]+1;
			dfs(y);
			siz[x]+=siz[y];
			if(siz[y]>siz[ch[x]])ch[x]=y;
		}
}

int dfn[MAXN],cnt; 

int bel[MAXN],top[MAXN],bel_cnt;

void dfs1(int x,int beln){
	dfn[x]=++cnt;
	bel[x]=beln;
	if(ch[x])dfs1(ch[x],beln);
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p[x]){
			if(y==ch[x])continue;
			top[++bel_cnt]=y;
			dfs1(y,bel_cnt);
		}
	if(ch[x])b[dfn[ch[x]]]=a[ch[x]]-a[x];
}

star rt;

inline void Init(){
	Scan(n);
	rep(i,1,n){
		int x,y;
		Scan(x),Scan(y);
		AddEdge(++x,++y);
	}
	rep(i,1,n+1)Scan(a[i]);
	dfs(1);
	top[++bel_cnt]=1;
	dfs1(1,bel_cnt);
	build(rt,1,n); 
}

int Q;

int bit[MAXN];

inline void Add(int x,int w){
	for(;x<=n;x+=x&-x)bit[x]+=w;
}
inline void Add(int l,int r,int w){
	if(l>r)return;
	Add(l,w),Add(r+1,-w);
}

inline int Sum(int x){
	int res=0;
	for(;x;x-=x&-x)res+=bit[x];
	return res;
}

inline void Query(int u,int v){
	int ans=0;
	int bu,bv;
	while((bu=top[bel[u]])!=(bv=top[bel[v]])){
		if(dep[bu]>dep[bv]){
			swap(bu,bv),swap(u,v);
		}
		int x=query(rt,1,n,dfn[bv],dfn[v]);
		x=gcd(x,Sum(dfn[bv])+a[bv]);
		ans=gcd(ans,x);
		v=p[bv];
	}
	if(dep[u]>dep[v])swap(u,v);
	ans=gcd(ans,query(rt,1,n,dfn[u]+1,dfn[v]));
	int x=Sum(dfn[u])+a[u];
	printf("%d\n",gcd(ans,x));
}

inline void modify(int x,int c){
	star p=pos[dfn[x]];
	if(!p)return;
	p->x+=c;
	for(p=p->p;p;p=p->p)p->update();
}

inline void Modify(int u,int v,int w){
	int bu,bv;
	while((bu=top[bel[u]])!=(bv=top[bel[v]])){
		if(dep[bu]>dep[bv]){
			swap(bu,bv),swap(u,v);
		}
		Add(dfn[bv],dfn[v],w);
		modify(ch[v],-w);
		v=p[bv];
	}
	if(dep[u]>dep[v])swap(u,v);
	Add(dfn[u],dfn[v],w);
	if(u!=top[bel[u]])modify(u,w);
	modify(ch[v],-w);
}

inline void Solve(){
	Scan(Q);
	rep(i,0,Q){
		char c; 
		while(c=g(),c<'A'||c>'Z');
		int u,v,w;
		Scan(u),Scan(v);
		++u,++v;
		if(c=='F')Query(u,v);
		else Scan(w),Modify(u,v,w);
	}
}

int main(){
	Init(); Solve(); return 0;
}