GCD Problem(线段树区间GCD+区间开方)

题目描述输入描述:

输出描述:

输入
4
5 45 20 65
7
1 1 4
0 1 4
1 1 4
1 3 4
0 3 4
1 3 4
1 2 2
输出
5
2
4
2
6

            两个操作,一个是区间开方,一个是输出区间GCD;gcd很好处理。主要是开放这个操作,假设区间sum==l-r+1就return,不是的话就取找辣个还不是1的点去单点更新,这样最多更新nlogn*8次左右(可能没算错~)~~就行了

#includebits/stdc++.h
using namespace std;
#define lson l,m,rt1
#define rson m+1,r,rt1|1
#define ll long long
const int maxn = 2e5 + 10;
ll gcd[maxn  2], sum[maxn  2];
long long GCD(long long a, long long b) {
	return b ? GCD(b, a%b) : a;
}
void pushup(int rt) {
	sum[rt] = sum[rt  1] + sum[rt  1 | 1];
	gcd[rt] = GCD(gcd[rt  1], gcd[rt  1 | 1]);
}
void build(int l, int r, int rt) {
	if (l == r) {
		scanf("%lld", sum[rt]);
		gcd[rt] = sum[rt];
		return;
	}
	int m = (l + r)  1;
	build(lson); build(rson);
	pushup(rt);
}
void updates(int L, int R, int l, int r, int rt) {
	if (sum[rt] == r - l + 1)return;
	if (l == r) {
		sum[rt] = sqrt(sum[rt]);
		gcd[rt] = sum[rt];
		return;
	}
	int m = (l + r)  1;
	if (L = m)updates(L, R, lson);
	if (m  R)updates(L, R, rson);
	pushup(rt);
}
ll query(int L, int R, int l, int r, int rt) {
	if (L = lr = R) {
		return gcd[rt];
	}
	int m = (l + r)  1;
	ll ans;
	if (L = m) {
		ans = query(L, R, lson);
		if (m  R) 
			ans = GCD(ans, query(L, R, rson));
	}
	else ans = query(L, R, rson);
	return ans;
}
int main() {
	int n;
	scanf("%d", n);
	build(1, n, 1);
	int q; scanf("%d", q);
	while (q--) {
		int a, b, c;
		scanf("%d%d%d", a, b, c);
		if (a == 1) {
			printf("%lld\n", query(b, c, 1, n, 1));
		}
		else {
			updates(b, c, 1, n, 1);
		}
	}
	return 0;
}

 

最新回复(0)
/jishubU1bVP06uiKITCqMd8Ltw_2FFYa9zw033_2FVDxJ6Q_3D_3D4794979
8 简首页