codechef Dynamic GCD
题意:给出一棵点权树，每次或者询问两点之间路径上所有点点权的gcd，或者把两点之间路径上所有点的点权同时加上一个数
考虑链上的做法，得到了链上做法之后在树上就只需要树链剖分就行了。
由更相减损术得，序列a1,a2,..,an的gcd等于序列a1,a2-a1,a3-a2,...,an-an-1的gcd。
那么对于链上我们就维护一阶差分的区间gcd，以及原数列的增量就好。
前一个信息我们用线段树维护，后一个信息我们用bit维护。
在树上的推广:用线段树维护每条重链的区间gcd，用bit维护每个点的增量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 | #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;} |
