学步园

2014 Multi-University Training Contest 3  

1007题

点击打开链接

单点修改，区间更新（线段树Lazy标记）

树状数组：

/*
优化：
1、用set容器记录num[i]还不是Nearest Fibonacci number的下标i,
操作三时只需要更新set中在区间内的数，num[i] -> Nearest Fibonacci number,同时把i
从set中移除。
直到遇到操作一时才可能再把它加进来。 所以这样就大大减少了操作三的耗时。
2、二分找 Nearest Fibonacci number。
3、输入加速。

只要有优化一就可以通过这一题。。。。
*/

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>

using namespace std;
typedef long long LL;

const int maxn = 100000 + 10;
int n, m;
LL C[maxn], num[maxn], f[maxn];
vector<int> vec;
set<int> s;

void Init()
{
    int  i;
    f[0]=1;
    f[1]=1;
    for(i=2; i<=91; i++) {
        f[i]=f[i-1]+f[i-2];
    }
}

int lowbit(int x)
{
    return x&(-x);
}
void update(int i, LL v)
{
    for(; i<=n; i += lowbit(i)) C[i] +=v;
}

LL getsum(int i)
{
    LL ret=0;
    for(; i>0; i-=lowbit(i)) ret +=C[i];
    return ret;
}

//适用于正整数
template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}

LL Find(LL x)
{
    int t = lower_bound(f,f+92, x) - f;
    LL k;
    if(t==0) k = 1;
    else {
        if(abs(f[t]- x)<abs(x-f[t-1])) k =f[t];
        else k = f[t-1];
    }
    return k;
}

int main()
{
    Init();
    int  i, j;
    int  a, b, c;
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d", &n, &m)) {
        memset(num, 0, sizeof(LL)*(n+2) );
        memset(C, 0, sizeof(LL)*(n+2) );
        s.clear();
        set<int>::iterator pos;
        for(i=1; i<=n; ++i) s.insert(i);
        while(m--) {
            scan_d(a);
            scan_d(b);
            scan_d(c);
            //scanf("%d%d%d", &a, &b, &c);
            if(a==1) {
                update(b, c);
                num[b] += c;
                s.insert(b);
            } else if(a==2) {
                LL ans = getsum(c) - getsum(b-1);
                printf("%I64d\n", ans);
            } else if(a==3) {
                vec.clear();
                for( pos = s.lower_bound(b); ((*pos)<=c)&&(pos!=s.end());pos++) {
                    int p = *pos;
                    LL New = Find(num[p]);  //num[p] -> Nearest Fibonacci number
                    update(p, New - num[p]);
                    num[p] = New;
                    vec.push_back(p);
                }

                for(i=0; i<vec.size(); ++i)
                    s.erase(vec[i]);
            }
        }
    }
    return 0;
}

线段树：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
struct node {
    int l, r;
    LL sum, fibsum;
    int lazy;
} tree[maxn*4];

LL f[100];
void calc_fib()
{
    int i;
    f[0] = f[1] = 1;
    for(i=2; i<=91; ++i) f[i] = f[i-1] + f[i-2];
}

LL Find(LL x)
{
    int t = lower_bound(f, f+92, x) - f;
    LL k;
    if(t==0) k = 1;
    else {
        if(abs(f[t]- x)<abs(x-f[t-1])) k = f[t];
        else k = f[t-1];
    }
    return k;
}

void PushUp(int rt)
{
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
    tree[rt].fibsum = tree[rt<<1].fibsum + tree[rt<<1|1].fibsum;
}

void PushDown(int rt)
{
    if(tree[rt].lazy) {
        tree[rt<<1].sum = tree[rt<<1].fibsum;
        tree[rt<<1|1].sum = tree[rt<<1|1].fibsum;
        tree[rt<<1].lazy = tree[rt<<1|1].lazy = 1;
        tree[rt].lazy = 0;
    }
}
void build(int rt, int l, int r)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].sum = tree[rt].fibsum = 0;
    tree[rt].lazy = 0;
    if(l == r) {
        tree[rt].sum = 0;
        tree[rt].fibsum = 1;
        return ;
    }
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    PushUp(rt);
}

void add(int rt, int pos, LL v)
{
    if(tree[rt].l == tree[rt].r) {
        tree[rt].lazy = 0;
        tree[rt].sum += v;
        tree[rt].fibsum = Find(tree[rt].sum );
        return ;
    }
    PushDown(rt);
    int mid = (tree[rt].l + tree[rt].r)>>1;
    if(pos<= mid)   add(rt<<1, pos, v);
    else            add(rt<<1|1, pos, v);
    PushUp(rt);
}

LL sum(int rt, int l, int r)
{
    if(l <= tree[rt].l && tree[rt].r <= r) {
        return tree[rt].sum;
    }
    PushDown(rt);
    int mid = (tree[rt].l + tree[rt].r)>>1;
    LL ret = 0;
    if(l<=mid) ret += sum(rt<<1, l, r);
    if(r > mid) ret += sum(rt<<1|1, l, r);
    return ret;
}

void update(int rt, int l, int r)
{
    if(l <= tree[rt].l && tree[rt].r <= r) {
        tree[rt].lazy = 1;
        tree[rt].sum = tree[rt].fibsum;
        return ;
    }
    PushDown(rt);
    int mid = (tree[rt].l + tree[rt].r)>>1;
    if(l<=mid) update(rt<<1, l, r);
    if(r >mid) update(rt<<1|1, l, r);
    PushUp(rt);
}

//适用于正整数
template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}

int main()
{
    int n, m;
    int op, l, r;
   // freopen("in.txt","r",stdin);
    calc_fib();
    while(~scanf("%d%d", &n, &m)) {
        build(1,1,n);
        while(m--) {
            scan_d(op);
            scan_d(l);
            scan_d(r);
            //scanf("%d%d%d", &op, &l, &r);
            if(op==1) add(1, l, r);
            if(op==2) printf("%I64d\n", sum(1, l, r));
            if(op==3) update(1, l, r);
        }
    }
    return 0;
}