Description#

Input#

Output#

每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input#

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

Sample Output#

101
11
11

题解#

本题和上帝造题的七分钟是一样的

但我的程序没有过啊
打的比较傻

其实只要维护一个值就可以了

用一个flag标记是否不变

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#ifndef LL
#define LL long long
#endif
#define lch l, m, rt << 1
#define rch m + 1, r, rt << 1 | 1
const int N = 100005;
LL Sum[N << 2];
bool flag[N << 2];
void PushUp(int rt)
{
	Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
	flag[rt] = flag[rt << 1] & flag[rt << 1 | 1];
}
void buildtree(int l, int r, int rt)
{
	if(l == r)
	{
		scanf("%lld", &Sum[rt]);
		if(Sum[rt] <= 1)
			flag[rt] = 1;
		return;
	}
	int m = l + r >> 1;
	buildtree(lch);
	buildtree(rch);
	PushUp(rt);
}
void Update(int L, int R, int l, int r, int rt)
{
	if(flag[rt])
		return;
	if(l == r)
	{
		Sum[rt] = sqrt(Sum[rt]);
		if(Sum[rt] <= 1)
			flag[rt] = 1;
		return;
	}
	int m = l + r >> 1;
	if (L <= m) Update(L, R, lch);
	if (R > m) Update(L, R, rch);
	PushUp(rt);
}
LL Query(int L, int R, int l, int r, int rt)
{
	if(L <= l && R >= r)
		return Sum[rt];
	int m = l + r >> 1;
	LL ans = 0;
	if (L <= m) ans += Query(L, R, lch);
	if (R > m) ans += Query(L, R, rch);
	return ans;
}
int main()
{
	int n;
	scanf("%d", &n);
	buildtree(1, n, 1);
	int m;
	scanf("%d", &m);
	while (m--)
	{
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if(l > r)
			swap(l, r);
		if (op == 1)
		{
			printf("%lld\n", Query(l, r, 1, n, 1));
		}
		else
			Update(l, r, 1, n, 1);
	}
}