首页 > 代码库 > hdu 4893 Wow! Such Sequence!（线段树功能：单点更新，区间更新相邻较小斐波那契数）

hdu 4893 Wow! Such Sequence!（线段树功能：单点更新，区间更新相邻较小斐波那契数）

2024-07-14 23:02:51   223人阅读

转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

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


----------------------------------------------------------------------------------------------------------------------------------------------------------
欢迎光临天资小屋害羞害羞害羞害羞：http://user.qzone.qq.com/593830943/main
----------------------------------------------------------------------------------------------------------------------------------------------------------


Problem Description
Recently, Doge got a funny birthday present from his new friend, Protein Tiger from St. Beeze College. No, not cactuses. It‘s a mysterious blackbox.

After some research, Doge found that the box is maintaining a sequence an of n numbers internally, initially all numbers are zero, and there are THREE "operations":

1.Add d to the k-th number of the sequence.
2.Query the sum of ai where l ≤ i ≤ r.
3.Change ai to the nearest Fibonacci number, where l ≤ i ≤ r.
4.Play sound "Chee-rio!", a bit useless.

Let F0 = 1,F1 = 1,Fibonacci number Fn is defined as Fn = Fn - 1 + Fn - 2 for n ≥ 2.
Nearest Fibonacci number of number x means the smallest Fn where |Fn - x| is also smallest.

Doge doesn‘t believe the machine could respond each request in less than 10ms. Help Doge figure out the reason.
 
Input
Input contains several test cases, please process till EOF.
For each test case, there will be one line containing two integers n, m.
Next m lines, each line indicates a query:

1 k d - "add"
2 l r - "query sum"
3 l r - "change to nearest Fibonacci"

1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231, all queries will be valid.
 
Output
For each Type 2 ("query sum") operation, output one line containing an integer represent the answer of this query.
 
Sample Input
1 1
2 1 1
5 4
1 1 7
1 3 17
3 2 4
2 1 5
 
Sample Output
0
22
 
Author
Fudan University
 
Source
2014 Multi-University Training Contest 3
 
Recommend
We have carefully selected several similar problems for you:  4896 4895 4894 4892 4891 


题目意思：
一个长度为n的数组，初始化为0，接下来m次操作，操作共有3种：
1 a b  即把数组中第a个位置的元素加b
2 a b  即求数组中[a,b]元素的总和
3 a b  把数组[a,b]中元素变成和该元素最相近的斐波那契数（若两个斐波那契数和该元素差的绝对值一样，取最小的斐波那契数）
 

思路：
 如果某一段已经进行过3操作，那么再次进行3操作时该段可以忽略。
 若某一段已经进行过3操作，且某几个元素进行过1操作，那么再次进行3操作时只需对这几个进行过1操作得元素变换斐波那契数即可。

代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
#define ll __int64
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define maxn 111111
ll num[maxn];
ll sum[maxn<<2];//求和
ll add[maxn<<2];
int se[maxn<<2];
ll f[111],x;
void Pushup(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	add[rt]=add[rt<<1]+add[rt<<1|1];
}
void build(int l,int r,int rt)
{
	sum[rt]=0;se[rt]=-1;
	if(l == r)
	{
		add[rt]=1;
		return ;
	}
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
	Pushup(rt);
}
void Pushdown(int rt,int l,int r)
{
	if(se[rt]!=-1)
	{
		sum[rt<<1]+=add[rt<<1];
		sum[rt<<1|1]+=add[rt<<1|1];
		add[rt<<1]=add[rt<<1|1]=0;
		se[rt<<1]=se[rt<<1|1]=1;
		se[rt]=-1;
	}
}
void update(int L,int R,ll c,int l,int r,int rt)
{
	if(L <= l && r <= R)
	{    
		sum[rt]+=c;
		int x=(int)(lower_bound(f,f+77,sum[rt])-f);//寻找相应的斐波那契数
		if(x == 0)
		{
			add[rt]=f[0]-sum[rt];
		}
		else
		{
			if(f[x]==sum[rt])
			{
				return ;
			}
			else if(sum[rt]-f[x-1]<=f[x]-sum[rt])//离的更近的
			{
				add[rt]=f[x-1]-sum[rt];
			}
			else 
				add[rt]=f[x]-sum[rt];
		}
		return ;
	}
	Pushdown(rt,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid)
		update(L,R,c,lson);
	if(mid < R)
		update(L,R,c,rson);
	Pushup(rt);

}
void ins(int L,int R,int l,int r,int rt)
{
	if(L<=l && r<=R)
	{
		sum[rt]+=add[rt];
		add[rt]=0; se[rt]=1;
		return ;
	}
	Pushdown(rt,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid)
		ins(L,R,lson);
	if(mid < R)
		ins(L,R,rson);
	Pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
	if(L<=l && r<=R)
	{
		return sum[rt];
	}
	Pushdown(rt,l,r);
	ll res=0;
	int mid = (l + r) >> 1;
	if(L <= mid)
		res+=query(L, R, lson);
	if(mid < R)
		res+=query(L, R, rson);
	return res;
}

int main()
{
	int n,m;
	f[0]=1;f[1]=1;
	for(int i=2;i<=77;++i)
		f[i]=f[i-1]+f[i-2];

	while(~scanf("%d%d",&n,&m))
	{
		build(1,n,1);
		int op,a,b;
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&op,&a,&b);
			if(op==1)
			{
				update(a,a,b,1,n,1);//单点增加区间为a->a;
			}
			else if(op==2)
			{
				printf("%I64d\n",query(a,b,1,n,1));
			}
			else if(op==3)
			{
				ins(a,b,1,n,1);
			}
		}
	}
	return 0;
}
































        

            
                
                  
                
                

                    联系

                    我们