CodeChef Dynamic GCD

嘟嘟嘟vjudge

我今天解决了一个历史遗留问题！

题意：给一棵树，写一个东西，支持一下两种操作：

1.\(x\)到\(y\)的路径上的每一个点的权值加\(d\)。

2.求\(x\)到\(y\)路径上所有点权的gcd。

树上路径操作自然能想到树剖，但问题在于区间加操作不好维护。

因此我们先考虑序列上的操作。

求gcd，方法除了辗转相除，还有更相减损之术啊！这个有一个非常好的性质，就是两数的gcd等于其中一个数和两数只差的gcd。两数之差，就让我们想到了差分。这样就能从区间修改变成了只修改连个点了！

因此我们维护两个东西：一是差分序列的区间gcd，支持单点修区间查；二是每一个数的权值，支持区间修单点查。对于一个修改区间\([L, R]\)，我们只改\(L\)和\([R + 1]\)的差分值，然后查询的时候只要求\(a[L]\)和\([L + 1, R]\)的gcd就搞定了。

现在变成了树上。这时候，修改的时候，修改单点应该是\(x\)的重儿子和\(x\)所在链顶端的点。

然后查询的时候，求的是每一条链顶端权值和从\(x\)开始往上直到顶端节点儿子的gcd。然后把所有的链的值一块gcd一下。

需要注意的是，如果所有数相等，那么差分序列全是0，这时候要特判：一个数和\(0\)的gcd还是它本身。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 5e4 + 5;

inline ll read()

{

	ll ans = 0;

	char ch = getchar(), last = ' ';

	while(!isdigit(ch)) last = ch, ch = getchar();

	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

	if(last == '-') ans = -ans;

	return ans;

}

inline void write(ll x)

{

	if(x < 0) x = -x, putchar('-');

	if(x >= 10) write(x / 10);

	putchar(x % 10 + '0');

}

char s[2];

int n, m, a[maxn];

struct Edge

{

	int nxt, to;

}e[maxn << 1];

int head[maxn], ecnt = -1;

In void addEdge(int x, int y)

{

	e[++ecnt] = (Edge){head[x], y};

	head[x] = ecnt;

}

int dep[maxn], fa[maxn], siz[maxn], son[maxn], dif[maxn];

In void dfs1(int now, int _f)

{

	siz[now] = 1; dif[now] = a[now] - a[_f];  //可能有负数

	for(int i = head[now], v; ~i; i = e[i].nxt)

	{

		if((v = e[i].to) == _f) continue;

		dep[v] = dep[now] + 1, fa[v] = now;

		dfs1(v, now);

		siz[now] += siz[v];

		if(!son[now] || siz[v] > siz[son[now]]) son[now] = v;

	}

}

int dfsx[maxn], pos[maxn], top[maxn], cnt = 0;

In void dfs2(int now, int _f)

{

	dfsx[now] = ++cnt; pos[cnt] = now;

	if(son[now]) top[son[now]] = top[now], dfs2(son[now], now);

	for(int i = head[now], v; ~i; i = e[i].nxt)

	{

		if((v = e[i].to) == _f || v == son[now]) continue;

		top[v] = v;

		dfs2(v, now);

	}

}

In int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

In int GCD(int a, int b)

{

	if(!a || !b) return a | b;

	return gcd(a, b);

}

int l[maxn << 2], r[maxn << 2], dat[maxn << 2], Gcd[maxn << 2], lzy[maxn << 2];

In void build(int L, int R, int now)

{

	l[now] = L, r[now] = R;

	if(L == R)

	{

		dat[now] = a[pos[L]];

		Gcd[now] = dif[pos[L]];

		return;

	}

	int mid = (L + R) >> 1;

	build(L, mid, now << 1);

	build(mid + 1, R, now << 1 | 1);

	Gcd[now] = GCD(abs(Gcd[now << 1]), abs(Gcd[now << 1 | 1]));

}

In void pushdown(int now)

{

	if(lzy[now])

	{

		dat[now << 1] += lzy[now]; dat[now << 1 | 1] += lzy[now];

		lzy[now << 1] += lzy[now]; lzy[now << 1 | 1] += lzy[now];

		lzy[now] = 0;

	}

}

In void update_Sin(int now, int id, int d)

{

	if(l[now] == r[now]) {Gcd[now] += d; return;}

	int mid = (l[now] + r[now]) >> 1;

	if(id <= mid) update_Sin(now << 1, id, d);

	else update_Sin(now << 1 | 1, id, d);

	Gcd[now] = GCD(abs(Gcd[now << 1]), abs(Gcd[now << 1 | 1]));

}

In void update_Lin(int L, int R, int now, int d)

{

	if(l[now] == L && r[now] == R)

	{

		dat[now] += d, lzy[now] += d;

		return;

	}

	pushdown(now);

	int mid = (l[now] + r[now]) >> 1;

	if(R <= mid) update_Lin(L, R, now << 1, d);

	else if(L > mid) update_Lin(L, R, now << 1 | 1, d);

	else update_Lin(L, mid, now << 1, d), update_Lin(mid + 1, R, now << 1 | 1, d);

}

In int query_Sin(int now, int id)

{

	if(l[now] == r[now]) return dat[now];

	pushdown(now);

	int mid = (l[now] + r[now]) >> 1;

	if(id <= mid) return query_Sin(now << 1, id);

	else return query_Sin(now << 1 | 1, id);

}

In int query_Lin(int L, int R, int now)

{

	if(l[now] == L && r[now] == R) return abs(Gcd[now]);

	int mid = (l[now] + r[now]) >> 1;

	if(R <= mid) return query_Lin(L, R, now << 1);

	else if(L > mid) return query_Lin(L, R, now << 1 | 1);

	else return GCD(query_Lin(L, mid, now << 1), query_Lin(mid + 1, R, now << 1 | 1));

}

In void update_path(int x, int y, int d)

{

	while(top[x] ^ top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x, y);

		if(son[x]) update_Sin(1, dfsx[son[x]], -d);

		update_Sin(1, dfsx[top[x]], d);

		update_Lin(dfsx[top[x]], dfsx[x], 1, d);

		x = fa[top[x]];

	}

	if(dep[x] < dep[y]) swap(x, y);

	if(son[x]) update_Sin(1, dfsx[son[x]], -d);

	update_Sin(1, dfsx[y], d);

	update_Lin(dfsx[y], dfsx[x], 1, d);

}

In int query_path(int x, int y)

{

	int ret = 0;

	while(top[x] ^ top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x, y);

		int tp = query_Sin(1, dfsx[top[x]]);

		if(x ^ top[x]) tp = GCD(tp, query_Lin(dfsx[top[x]] + 1, dfsx[x], 1));

		ret = ret ? GCD(ret, tp) : tp;

		x = fa[top[x]];

	}

	if(dep[x] < dep[y]) swap(x, y);

	int tp = query_Sin(1, dfsx[y]);

	if(x ^ y) tp = GCD(tp, query_Lin(dfsx[y] + 1, dfsx[x], 1));

	ret = ret ? GCD(ret, tp) : tp;

	return ret;

}

int main()

{

	Mem(head, -1);

	n = read();

	for(int i = 1; i < n; ++i)

	{

		int x = read() + 1, y = read() + 1;

		addEdge(x, y), addEdge(y, x);

	}

	for(int i = 1; i <= n; ++i) a[i] = read();

	dfs1(1, 0), top[1] = 1, dfs2(1, 0);

	build(1, n, 1);

	m = read();

	for(int i = 1; i <= m; ++i)

	{

		scanf("%s", s); int x = read() + 1, y = read() + 1;

		if(s[0] == 'C')

		{

			int d = read();

			update_path(x, y, d);

		}

		else write(query_path(x, y)), enter;

	}

	return 0;

}

巴特西

CodeChef Dynamic GCD

最新文章

热门文章