hdu 4983 线段树+斐波那契数

http://acm.hdu.edu.cn/showproblem.php?pid=4893

三种操作：

1 k d，修改k的为值增加d

2 l r，查询l到r的区间和

3 l r，从l到r区间上的所以数变成最近的斐波那契数，相等的话取向下取。

就是线段树搞，每个节点lazy表示该节点以下的位置是否都是斐波那契数，找比x小的斐波那契数使用lower_bound+加特判最近即可

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const int N = 100005;

const LL inf = 1LL<<60;

struct node

{

    int lazy;

    LL sum,r;

}s[N<<3];

LL c[N];

LL f[1500];

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

{

    s[root].sum = 0;

    s[root].r = r - l + 1;

    s[root].lazy = 0;

    if(l == r){

        return;

    }

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

    build(l,mid,root<<1);

    build(mid+1,r,(root<<1)+1);

    return;

}

LL check(LL x){

    int t = lower_bound(f,f+1426,x) - f;

    long long delta = abs(f[t]-x);

    if (t > 0 && abs(f[t-1] - x) <= delta) --t;

    return f[t];

}

void update(int root)

{

    s[root].sum = s[root<<1].sum + s[root<<1|1].sum;

    s[root].r = s[root<<1].r + s[root<<1|1].r;

}

void insert(int l,int r,int root,int index,int v)

{

    if(l == r){

        s[root].sum += v;

        s[root].r = check(s[root].sum);

        return;

    }

    if(s[root].lazy){

        s[root<<1].lazy = 1;

        s[root<<1].sum = s[root<<1].r;

        s[root<<1|1].lazy = 1;

        s[root<<1|1].sum = s[root<<1|1].r;

        s[root].lazy = 0;

    }

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

    if(mid >= index)

        insert(l,mid,root<<1,index,v);

    else

        insert(mid+1,r,(root<<1)+1,index,v);

    update(root);

}

LL query(int l , int r , int root , int ll , int rr){

    if (l > rr || r < ll) return 0;

    if(s[root].lazy){

        s[root<<1].lazy = 1;

        s[root<<1].sum = s[root<<1].r;

        s[root<<1|1].lazy = 1;

        s[root<<1|1].sum = s[root<<1|1].r;

        s[root].lazy = 0;

    }

    if (ll <= l && rr >= r) return s[root].sum;

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

    return query(l,mid,root<<1,ll,rr) + query(mid+1,r,(root<<1)+1,ll,rr);

}

void change(int l , int r , int root, int ll , int rr){

    if (l > rr || r < ll) return;

    if (ll <= l && rr >= r){

           s[root].lazy = 1;

           s[root].sum = s[root].r;

           return;

    }

    if(s[root].lazy){

        s[root<<1].lazy = 1;

        s[root<<1].sum = s[root<<1].r;

        s[root<<1|1].lazy = 1;

        s[root<<1|1].sum = s[root<<1|1].r;

        s[root].lazy = 0;

    }

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

    change(l,mid,root<<1,ll,rr);

    change(mid+1,r,(root<<1)+1,ll,rr);

    update(root);

}

int main()

{

    f[0] = f[1] = 1LL;

    int i;

    for(i = 2;i < 1426;++i)

        f[i] = f[i-1]+f[i-2];

    int n,m;

    while(~RD2(n,m)){

        clr0(c);

        build(1,n,1);

        int l,r,q;

        while(m--){

            scanf("%d%d%d",&q,&l,&r);

            if(q == 1)

                insert(1,n,1,l,r);

            else if(q == 2)

                printf("%I64d\n",query(1,n,1,l,r));

            else

                change(1,n,1,l,r);

        }

    }

    return 0;

}

巴特西

hdu 4983 线段树+斐波那契数

最新文章

热门文章