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

HINT

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9


Source

SPOJ2713 gss4 数据已加强


一颗线段树码出来， 对于每个修改，找到单点修改即可。

没了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define N 100010
#define ll long long
#define lson l, mid, lx
#define rson mid + 1, r, rx
using namespace std;
struct Tree
{
	int l, r;
	ll sum;
	bool flag;
}t[N * 4];
int n, m;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

void build(int l, int r, int rt)
{
	t[rt].l = l;
	t[rt].r = r;
	int lx = rt << 1, rx = rt << 1 | 1;
	if(l == r)
	{
		t[rt].sum = read();
		t[rt].l = t[rt].r = t[rt].sum;
		if(t[rt].sum == 0 || t[rt].sum == 1)
			t[rt].flag = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
	t[rt].sum = t[lx].sum + t[rx].sum;
	t[rt].flag = t[lx].flag & t[rx].flag;
}

ll query(int l, int r, int rt, int x, int y)
{
	if(l == x && r == y) return t[rt].sum;
	int mid = (l + r) >> 1;
	int lx = rt << 1, rx = rt << 1 | 1;
	if(mid < x) return query(rson, x, y);
	else if(mid >= y) return query(lson, x, y);
	else return query(lson, x, mid) + query(rson, mid + 1, y);
}

void update(int l, int r, int rt, int x, int y)
{
	if(t[rt].flag == 1) return;
	if(l == r)
	{
		t[rt].sum = sqrt(t[rt].sum);
		if(t[rt].sum == 0 || t[rt].sum == 1) 
			t[rt].flag = 1;
		return;
	}
	int lx = rt << 1, rx = rt << 1 | 1;
	int mid = (l + r) >> 1;
	if(mid >= y) update(lson, x, y);
	else if(mid < x) update(rson, x, y);
	else update(lson, x, mid), update(rson, mid + 1, y);
	t[rt].sum = t[lx].sum + t[rx].sum;
	t[rt].flag = t[lx].flag & t[rx].flag;
}

int main()
{
	n = read();
	build(1, n, 1);
	m = read();
	for(int i = 1; i <= m; i ++)
	{
		int f, x, y;
		f = read();
		x = read();
		y = read();
		if(x > y) swap(x, y);
		switch(f)
		{
			case 1:printf("%lld\n", query(1, n, 1, x, y));break;
			case 2:update(1, n, 1, x, y);break;
		}

	}	
	return 0;
}