DDOSvoid's Blog

第十七届浙大城市学院程序设计竞赛 K Sumo and Fibonacci

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目描述

https://ac.nowcoder.com/acm/contest/21733/K

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问求区间 $[l,r]$ 中的所有数排序去重后得到的序列 $b_i$，这个区间的价值是 $\sum b_if_i$，其中 $f_i$ 表示斐波那契数列第 $i$ 项

$n,m\le 3\times 10^4$

Solution

通过 $n,m$ 的范围容易判断 $n\sqrt n\log n$ 的算法应该可以通过

所以我们直接考虑莫队，现在的问题是加入和删除某个数如何维护答案

我们将 $f_i$ 看成指数的形式，即 $k^i$，对于形如 $\sum a_ik^i$ 的形式可以用线段树维护，合并左右子树时，需要将右子树 $\sum a_ik^i$ 变成 $\sum a_ik^{i+T[lc]}$，对于 $k^{i+T[lc]}$ 可以直接将 $k^{T[lc]}$ 提出来，对于斐波那契数，我们考察斐波那契数的矩阵转移，容易将斐波那契数写成 $k^i$ 的形式

因为矩阵只有 $2\times 2$，所以我们将其拆开来写常数应该比较小，另外需要预处理斐波那契数转移矩阵的 $n$ 次方，加入和删除我们看成单点修改即可

时间复杂度 $O(n\sqrt n\log n)$

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
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>
#include <set>
#include <cmath>
#define maxn 30010
#define ll long long
#define INF 1000000000
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

int n, m, a[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b; 
}

int blo; 
struct Query {
    int l, r, id;

    friend bool operator < (const Query &u, const Query &v) {
        if (u.l / blo == v.l / blo) return (u.l / blo & 1) ? u.r < v.r : u.r > v.r;
        return u.l < v.l;
    }
} Q[maxn];

struct Matrix {
    static const int n = 2; 
    int a[n + 1][n + 1];
    
    inline void clear() { fill(a[0], a[0] + (n + 1) * (n + 1), 0); }
    
    Matrix() { clear(); }
    
    inline void setone() { for (int i = 1; i <= n; ++i) a[i][i] = 1; }

    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix w; 
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    w.a[i][j] = add(w.a[i][j], 1ll * u.a[i][k] * v.a[k][j] % p);
        return w;
    }
} s[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll v, pre; int sz;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].sz = T[lc].sz + T[rc].sz;
    T[i].v = (T[lc].v + T[rc].v * s[T[lc].sz].a[1][1] + T[rc].pre * s[T[lc].sz].a[1][2]) % p;
    T[i].pre = (T[lc].pre + T[rc].v * s[T[lc].sz].a[2][1] + T[rc].pre * s[T[lc].sz].a[2][2]) % p;
}

void update(int i, int l, int r, int k, int v) {
    if (l == r) return T[i] = { v * b[k], 0, v }, void();
    int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, v);
    else update(rc, m + 1, r, k, v);
    maintain(i); 
}

int num[maxn];
void add(int x) { if (++num[x] == 1) update(1, 1, cnt, x, 1); }

void del(int x) { if (--num[x] == 0) update(1, 1, cnt, x, 0); }

int ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; blo = sqrt(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_hash();
    s[0].setone(); s[1].a[1][1] = s[1].a[1][2] = s[1].a[2][1] = 1;
    for (int i = 2; i <= n; ++i) s[i] = s[i - 1] * s[1];
    cin >> m; 
    for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
    sort(Q + 1, Q + m + 1);
    int l = Q[1].l, r = Q[1].l - 1;
    for (int i = 1; i <= m; ++i) {
        while (r < Q[i].r) add(a[++r]);
        while (l > Q[i].l) add(a[--l]);
        while (r > Q[i].r) del(a[r--]);
        while (l < Q[i].l) del(a[l++]);
        ans[Q[i].id] = T[1].v;
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0; 
}