Wow! Such Sequence!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 352 Accepted Submission(s): 104
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.
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.
1 1 2 1 1 5 4 1 1 7 1 3 17 3 2 4 2 1 5
0 22
题意：
给你长度为n的序列。序列初始值都为0.m组询问。支持三种操作。
1 k d 给第k个数加上d。
2 l r 询问[l.r]区间和。
3 l r 把所有[l,r]的值a[i]变成与a[i]值最相近的费布拉奇数。
f[0]=1,f[1]=1.f[i]=f[i-1]+f[i-2].
1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231
思路：
本来不打算写题解的。但是搜了下网上的题解。发现方法都不是很好。于是打算分享下自己的方法。
对于前两个操作肯定很简单啦。关键是现在有了第三个操作。其实很简单。我们只需在线段树的没个结点维护两个信息sum表示原区间和。和假如把整个区间变成费布拉奇数的区间和fsum.再加上一个ff标记表示区间是否都是费布拉奇数。对于add操作。单点更新。没什么优化只是更新后沿途更新下sum,fsum.ff就行了。只是更新叶子结点的fsum.先打个大小90的费布拉奇数列表。再二分找最近的值就行。。对于3操作就更简单了。如果当前区间的ff标记为1就不用更新了。不然就往下更新。直到区间匹配让后sum=fsum。再打上标记就行了。对于询问操做跟区间求和没什么区别。需要注意的是数据要爆int。这个应该自己可以看出来。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
ll f[110];
ll sum[maxn<<2],fsum[maxn<<2];
bool ff[maxn<<2];
ll getf(ll x)
{
int low=0,hi=90,mid,ans;
if(x<=0)
return 1LL;
while(low<=hi)
{
mid=(low+hi)>>1;
if(f[mid]<=x)
ans=mid,low=mid+1;
else
hi=mid-1;
}
if(f[ans+1]-x<x-f[ans])
return f[ans+1];
else
return f[ans];
}
void build(int L,int R,int rt)
{
ff[rt]=false;
sum[rt]=0;
fsum[rt]=R-L+1;//比赛时短路.fsum=1.wa了一发。
if(L==R)
return;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void PushDown(int L,int R,int rt)
{
int ls=rt<<1,rs=ls|1;
ff[rt]=false;
ff[ls]=ff[rs]=true;
sum[ls]=fsum[ls];
sum[rs]=fsum[rs];
}
void add(int L,int R,int rt,int p,ll v)
{
if(L==R)
{
ff[rt]=false;
sum[rt]+=v;
fsum[rt]=getf(sum[rt]);
return ;
}
if(ff[rt])
PushDown(L,R,rt);
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p<=mid)
add(lson,p,v);
else
add(rson,p,v);
sum[rt]=sum[ls]+sum[rs];
fsum[rt]=fsum[ls]+fsum[rs];
}
void update(int L,int R,int rt,int l,int r)
{
if(ff[rt])
return;
if(l<=L&&R<=r)
{
ff[rt]=true;
sum[rt]=fsum[rt];
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(l<=mid)
update(lson,l,r);
if(r>mid)
update(rson,l,r);
if(ff[ls]&&ff[rs])
ff[rt]=true;
sum[rt]=sum[ls]+sum[rs];
fsum[rt]=fsum[ls]+fsum[rs];
}
ll qu(int L,int R,int rt,int l,int r)
{
ll tp=0;
if(l<=L&&R<=r)
return sum[rt];
if(ff[rt])
PushDown(L,R,rt);
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(l<=mid)
tp=qu(lson,l,r);
if(r>mid)
tp+=qu(rson,l,r);
sum[rt]=sum[ls]+sum[rs];
fsum[rt]=fsum[ls]+fsum[rs];
return tp;
}
int main()
{
int i,n,m,cmd,a;
ll b;
f[0]=f[1]=1;
for(i=2;i<=90;i++)
f[i]=f[i-1]+f[i-2];
while(~scanf("%d%d",&n,&m))
{
build(1,n,1);
for(i=0;i<m;i++)
{
scanf("%d%d%I64d",&cmd,&a,&b);
if(cmd==1)
add(1,n,1,a,b);
else if(cmd==2)
printf("%I64d\n",qu(1,n,1,a,b));
else
update(1,n,1,a,b);
}
}
return 0;
}
