【SP2713 GSS4 - Can you answer these queries IV】 题解

题目链接：https://www.luogu.org/problemnew/show/SP2713

真暴力啊。

开方你开就是了，开上6次就都没了。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int maxn = 100100;

inline ll read(){

    ll k = 0 ; char c = getchar() ;

    while (!isdigit(c)) c = getchar() ;

    while (isdigit(c)) k = k * 10 + c - 48, c = getchar() ;

    return k  ;

}

ll n, m, a[maxn], t=0;

class Segment_Tree{

	#define lson l, mid, rt<<1

	#define rson mid+1, r, rt<<1|1

	public:

		ll tree[maxn<<2];

		void build(ll l, ll r, ll rt)

		{

			if(l == r)

			{

				tree[rt] = a[l];

				return;

			}

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

			build(lson);

			build(rson);

			PushUP(rt);

		}

		void update(ll left, ll right, ll l, ll r, ll rt)

		{

			if(left <= l && r <= right)

			{

				if(tree[rt] <= r - l + 1) return;

				else

				{

					if(l == r)

					{

						tree[rt] = (ll)sqrt((double)tree[rt]);

						return;

					}

				}

			}

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

			PushUP(rt);

			if(left <= mid) update(left, right, lson);

			PushUP(rt);

			if(right > mid) update(left, right, rson);

			PushUP(rt);

		}

		ll query(ll left, ll right, ll l, ll r, ll rt)

		{

			ll res = 0;

			if(left <= l && right >= r)

			{

				return tree[rt];

			}

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

			if(left <= mid) res += query(left, right, lson);

			if(right > mid) res += query(left, right, rson);

			return res;

		}

	private:

		void PushUP(ll rt)

		{

			tree[rt] = tree[rt<<1] + tree[rt<<1|1];

		}

}T;

int main()

{

	while(~scanf("%lld",&n))

	{

		t++;

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

		memset(a, 0, sizeof(a));

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

		a[i] = read();

		T.build(1,n,1);

		m = read();

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

		{

			ll opt, x, y;

			opt = read();

			x = read();

			y = read();

			if(y < x) swap(x, y);

			if(opt == 0)

			T.update(x,y,1,n,1);

			else

			printf("%lld\n",T.query(x,y,1,n,1));

		}

	}

	return 0;

}