程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> T - Can you answer these queries?（單點更新，線段樹優化）

T - Can you answer these queries?（單點更新，線段樹優化）

編輯：C++入門知識

T - Can you answer these queries?（單點更新，線段樹優化）

對n個整數有m個操作，共有兩種操作：0 l r表示把區間[l,r]之間的數開方，1 l r表示詢問[l,r]的和。

開方即單點更新。但所有的數都單點更新和模擬每什麼差別。重點就是成段維護區間的和，因為當操作次數相當多時，這些數大部分就會變成1，因此可以用線段樹維護區間的和，當這個區間的數全部是1就沒必要更新了。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL long long
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;

struct node
{
	int l,r;
	LL sum;
}tree[maxn*4];

LL a[maxn];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	if(l == r)
	{
		tree[v].sum = a[l];
		return;
	}
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
	tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;
}

void update(int v, int l, int r)
{
	if(tree[v].sum == tree[v].r - tree[v].l + 1)
		return;
	if(tree[v].l == tree[v].r)
	{
		tree[v].sum = sqrt(tree[v].sum*1.0);
		return;
	}
	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		update(v*2,l,r);
	else if(l > mid)
		update(v*2+1,l,r);
	else
	{
		update(v*2,l,mid);
		update(v*2+1,mid+1,r);
	}
	tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;
}

LL query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
		return tree[v].sum;
	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		return query(v*2,l,r);
	else if(l > mid)
		return query(v*2+1,l,r);
	else
		return query(v*2,l,mid) + query(v*2+1,mid+1,r);
}

int main()
{
	int n,m,item = 1;
	int x,l,r;

	while(~scanf(%d,&n))
	{
		for(int i = 1; i <= n; i++)
			scanf(%I64d,&a[i]);
		build(1,1,n);
		scanf(%d,&m);
		printf(Case #%d:
,item++);
		while(m--)
		{
			scanf(%d %d %d,&x,&l,&r);
			if(l > r)
				swap(l,r);
			if(x == 0)
				update(1,l,r);
			else
				printf(%I64d
,query(1,l,r));
		}
		printf(
);
	}
	return 0;
}