Algoogle

Algorithm for Programming Contest

Codeforces 446C DZY Loves Fibonacci Numbers

Category: Codeforces Tag: sqrt-decomposition

DZY Loves Fibonacci Numbers

問題概要


長さn(<=300000)の数列aと, Fibonacci数列fを考えるとき以下のクエリを処理しろ.

  • aの区間[l,r]の要素a[i]にそれぞれf[i-l]を加える
  • aの区間[l,r]の要素の合計値をmod 1e9+9で答える

解法


分割の大きさをBとして平方分割する.
加えるときは分割された区間を覆う場合は一気に足すのと端っこが余った場合はナイーブにaに足していく.
またいままで区間に足されたFibonacci数の始め2項をそれぞれ和として保存しておく.

復元するときは分割された区間を覆う場合はその部分は一気に足し合わせる.
端っこの余った部分はナイーブにaを足し合わせるのと, その区間に一気に足し合わせたFibonacci数の始めの2項のそれぞれの総和から各aに一気に足されたFibonacci数を復元する.
に足されたFibonacci数の総和の復元はj番目のFibonacci数をとし, その区間に一気に足されたFibonacci数の最初の2項のそれぞれの総和をu, vとすると
でできる.
あとはこれでは微妙にTLEしまくるので分割の大きさとか定数倍高速化とか頑張る(恐らく平方分割は想定解法でなくTLEするようになっている)

コード


(446C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
using namespace std;

const int mod = 1e9+9;
const int B = 550;

int n, m, a[300010], f[300010], sum[300010];
int qs[1000], nv[1000][2], i;

void gen(){
    f[0] = f[1] = 1;
    for(i=0;i<n;++i) f[i+2] = (f[i]+f[i+1])%mod, sum[i+1] = (sum[i]+f[i])%mod;
    for(i=0;i<n;++i) qs[i/B] = (qs[i/B]+a[i])%mod;
}

void update(int l, int r){
    int li = 0, ri = r-l;
    for(;l%B and l<r;++l,++li){
        qs[l/B] = (qs[l/B]+f[li])%mod;
        a[l] = (a[l]+f[li])%mod;
    }
    while(r%B and l < r){
        --r; --ri;
        qs[r/B] = (qs[r/B]+f[ri])%mod;
        a[r] = (a[r]+f[ri])%mod;
    }
    for(i=l/B;i<r/B;++i,li+=B){
        qs[i] = (qs[i]+(sum[li+B]-sum[li]+mod)%mod)%mod;
        nv[i][0] = (nv[i][0]+f[li])%mod;
        nv[i][1] = (nv[i][1]+f[li+1])%mod;
    }
}

int query(int l, int r){
    int ret = 0;
    if(l%B>B/2 or l/B==r/B){
        for(;l%B and l<r; ++l){
            ret = (ret+a[l])%mod;
            if(l%B>1) ret = (ret+1LL*f[l%B-1]*nv[l/B][1]+1LL*f[l%B-2]*nv[l/B][0])%mod;
            else ret = (ret+nv[l/B][l%B])%mod;
        }
    }
    else{
        while(l%B) {
            --l;
            ret = (ret-a[l]+mod)%mod;
            if(l%B>1) ret = (ret-(1LL*f[l%B-1]*nv[l/B][1]%mod+1LL*f[l%B-2]*nv[l/B][0]%mod)%mod+mod)%mod;
            else ret = (ret-nv[l/B][l%B]+mod)%mod;
        }
    }
    if(r%B<B/2){
        while(r%B and l < r){
            --r;
            ret = (ret+a[r])%mod;
            if(r%B>1) ret = (ret+1LL*f[r%B-1]*nv[r/B][1]+1LL*f[r%B-2]*nv[r/B][0])%mod;
            else ret = (ret+nv[r/B][r%B])%mod;
        }
    }
    else {
        for(;r%B and l<r; ++r){
            ret = (ret-a[r]+mod)%mod;
            if(r%B>1) ret = (ret-(1LL*f[r%B-1]*nv[r/B][1]%mod+1LL*f[r%B-2]*nv[r/B][0]%mod)%mod+mod)%mod;
            else ret = (ret-nv[r/B][r%B]+mod)%mod;
        }
    }
    for(i=l/B;i<r/B;++i)
        ret = (ret+qs[i])%mod;
    return ret;
}

void solve(){
    gen();
    int l, r, tp;
    while(m--){
        scanf("%d%d%d", &tp, &l, &r);
        l--;
        if(tp==1) update(l,r);
        else printf("%d\n", query(l,r));
    }
}

void input(){
    scanf("%d%d", &n, &m);
    for(i=0;i<n;++i) scanf("%d", a+i);
}

int main(){
    input();
    solve();
    return 0;
}

Comments