【线段树 成段更新】HDU 4027

KIDx的解题报告

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027

 加了输入外挂之后，排第二，还不错！

下面的代码没加外挂，运行时间是：375ms，还可以

#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define Max 26
#define LL __int64

struct Node{
	int l, r;
	LL v;
}N[M<<2];

LL v[M];
void create (int u, int a, int b)
{
	N[u].l = a, N[u].r = b;
	if (a == b)
	{
		N[u].v = v[a];
		return ;
	}
	int mid = (a + b) >> 1, lc = u+u, rc = u+u+1;
	create (lc, a, mid);
	create (rc, mid+1, b);
	N[u].v = N[lc].v + N[rc].v;
}

void update (int u, int a, int b)
{
	if (N[u].v == N[u].r - N[u].l + 1)			//说明从l到r都是1，不用往下更新了
		return ;
	if (N[u].l == N[u].r)
	{
		N[u].v = LL(sqrt ((double)N[u].v));		//自底向上更新
		return ;
	}
	int lc = u+u, rc = u+u+1;
	if (a <= N[lc].r)
		update (lc, a, b);
	if (b >= N[rc].l)
		update (rc, a, b);
	N[u].v = N[lc].v + N[rc].v;
}

LL find (int u, int a, int b)
{
	if (N[u].v == N[u].r - N[u].l + 1)			//同理lazy一下
		return min (N[u].r, b) - max (N[u].l, a) + 1;
	if (a <= N[u].l && b >= N[u].r)
		return N[u].v;
	LL m1 = 0, m2 = 0;
	int lc = u+u, rc = u+u+1;
	if (a <= N[lc].r)
		m1 = find (lc, a, b);
	if (b >= N[rc].l)
		m2 = find (rc, a, b);
	return m1+m2;
}

int main()
{
	char ch[2];
	int n, i, m, cc = 1, a, b;
	while (~scanf ("%d", &n))
	{
		for (i = 1; i <= n; i++)
			scanf ("%I64d", v+i);
		create (1, 1, n);
		scanf ("%d", &m);
		printf ("Case #%d:\n", cc++);
		while (m--)
		{
			scanf ("%s%d%d", ch, &a, &b);
			if (a > b) a ^= b, b ^= a, a ^= b;	//又是坑人的陷阱
			if (ch[0] == '1') printf ("%I64d\n", find (1, a, b));
			else update (1, a, b);
		}
		printf ("\n");
	}
    return 0;
}