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次左右（可能没算错~）~~就行了

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|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 <= l&&r <= 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;
}