首页 > 代码库 > hdu 4893 (多校1007)Wow! Such Sequence!(线段树&二分&思维)

hdu 4893 (多校1007)Wow! Such Sequence!(线段树&二分&思维)

2024-07-14 18:09:42   223人阅读

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


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
 

Source
2014 Multi-University Training Contest 3
 

Recommend
hujie   |   We have carefully selected several similar problems for you:  4896 4895 4894 4892 4891 
 

题意：

给你长度为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;
}




联系
我们