「SP2713」GSS4 - Can you answer these queries IV

传送门

Luogu

解题思路

区间开方以及区间求和。

考虑用线段树来做。

开方操作看似没有任何结合律可言，但这题有另外一个性质：

一个数的初始值不超过 \(10^{18}\) ，而这个数被开方6次左右就可以到1或0，并且1和0都是不需要再开方的。

所以我们记一下每个节点代表区间的最大值，若该值小于等于1，那么就不需要再进入下一层递归，否则就向下递归修改，修改次数最坏也不过是 \(O(6n)\) 左右，线段树完全没压力，于是这题就做完了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

typedef long long LL;

const int _ = 100010;

int n; LL a[_], sum[_ << 2], mx[_ << 2];

inline int lc(int rt) { return rt << 1; }

inline int rc(int rt) { return rt << 1 | 1; }

inline void pushup(int rt) {

	sum[rt] = sum[lc(rt)] + sum[rc(rt)];

	mx[rt] = max(mx[lc(rt)], mx[rc(rt)]);

}

inline void build(int rt = 1, int l = 1, int r = n) {

	if (l == r) { mx[rt] = sum[rt] = a[l]; return; }

	int mid = (l + r) >> 1;

	build(lc(rt), l, mid), build(rc(rt), mid + 1, r), pushup(rt);

}

inline void update(int ql, int qr, int rt = 1, int l = 1, int r = n) {

	if (mx[rt] <= 1) return;

	if (l == r) { mx[rt] = sum[rt] = sqrt(sum[rt]); return; }

	int mid = (l + r) >> 1;

	if (ql <= mid) update(ql, qr, lc(rt), l, mid);

	if (qr > mid) update(ql, qr, rc(rt), mid + 1, r);

	pushup(rt);

}

inline LL query(int ql, int qr, int rt = 1, int l = 1, int r = n) {

	if (ql <= l && r <= qr) return sum[rt];

	int mid = (l + r) >> 1; LL res = 0;

	if (ql <= mid) res += query(ql, qr, lc(rt), l, mid);

	if (qr > mid) res += query(ql, qr, rc(rt), mid + 1, r);

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	int Case = 0;

	while (scanf("%d", &n) != EOF) {

		printf("Case #%d:\n", ++Case);

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

		build();

		int q; read(q);

		for (rg int f, ql, qr; q--; ) {

			read(f), read(ql), read(qr);

			if (ql > qr) swap(ql, qr);

			if (!f) update(ql, qr);

			else printf("%lld\n", query(ql, qr));

		}

		puts("");

	}

	return 0;

}

完结撒花 \(qwq\)

巴特西

「SP2713」GSS4 - Can you answer these queries IV

解题思路

细节注意事项

参考代码

最新文章

热门文章