Can you answer these queries? HDU 4027 线段树

题意

是说有从1到编号的船，每个船都有自己战斗值，然后我方有一个秘密武器，可以使得从一段编号内的船的战斗值变为原来值开根号下的值。有两种操作，第一种就是上面描述的那种，第二种就是询问某个区间内的船的战斗值的总和。

解题思路

使用线段树就不用多说了，关键是如果不优化的话会超时，因为每次修改都是需要递归到叶子节点，很麻烦，但是我们发现，如果一个叶子节点的值已经是1的话，那个再开方它也是1，不变，这样我们就只需要判断父节点的值是不是区间的长度就可以了。

具体就在update函数里面。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<iostream>

#include<cmath>

# define ls (rt<<1)

# define rs (rt<<1|1)

using namespace std;

typedef long long ll;

const int  maxn=1e5+7;

struct node{

	int l, r;

	ll sum;

}t[maxn<<2];

ll num[maxn];

int n, m;

void up(int rt)

{

	t[rt].sum=t[ls].sum+t[rs].sum;

}

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

{

	t[rt].l=l;

	t[rt].r=r;

	if(l==r)

	{

		t[rt].sum=num[l];

		return ;

	}

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

	build(ls, l, mid);

	build(rs, mid+1, r);

	up(rt);

}

void update(int rt, int l, int r)

{

	if(t[rt].sum==t[rt].r - t[rt].l+1) //如果发现父节点的值等于它的区间长度的话就可直接返回了，不用再进行递归。

	{

		return ;

	}

	if(t[rt].l==t[rt].r )

	{

		t[rt].sum=(ll)sqrt(t[rt].sum);

		return ;

	}

	int mid=(t[rt].l+t[rt].r)>>1;

	if(l<=mid) update(ls, l, r);

	if(r>mid)  update(rs, l, r);

	up(rt);

}

ll query(int rt, int l, int r)

{

	if(l <= t[rt].l && t[rt].r <= r)

	{

		return t[rt].sum;

	}

	ll ans=0;

	int mid=(t[rt].l+t[rt].r)>>1;

	if(l<=mid) ans+=query(ls, l, r);

	if(r>mid) ans+=query(rs, l, r);

	return ans;

}

int main()

{

	int ca=1;

	while(scanf("%d", &n)!=EOF)

	{

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

		{

			scanf("%lld", &num[i]);

		}

		build(1, 1, n);

		int op;

		int x, y;

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

		scanf("%d", &m);

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

		{

			scanf("%d%d%d", &op, &x, &y);

			if(op==1)

			{

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

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

			}

			else

			{

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

				update(1, x, y);

			}

		}

		printf("\n");

	}

	return 0;

}

巴特西

Can you answer these queries? HDU 4027 线段树

Can you answer these queries? HDU 4027 线段树

题意

解题思路

代码实现

最新文章

热门文章