首页 > 编程学习 > CF633H Fibonacci-ish II

CF633H Fibonacci-ish II

发布时间:2022/9/3 7:28:13

传送门


思路

考虑使用莫队

当加入一个数时,如果不是第一次加入,就不用管它;

否则,我们在权值线段树上记录它的贡献

为了方便修改,线段树上需要记录的是:它的排名减一的斐波那契数与它的乘积,以及它的排名的斐波那契数与它的乘积,记为 \(pre,sum\)

假如我们加入一个数 \(x\),那我们需要统计 \(1\) ~ \(x-1\) 上已经有多少个数,用来求 \(x\) 的排名;而 \(x+1\) ~ \(m\)\(m\) 是最大值)的 \(pre,sum\) 就要相应变成 \(sum, pre+sum\)

实际上,如果 \(pre,sum\) 要变动 \(x\) 次,那么新值的计算方式为:

\[npre=f[x-1]*pre+f[x]*sum \]

\[nsum=f[x]*pre+f[x+1]*sum \]

因此我们就可以打懒标记节省时间

类似的,对于删除一个数,如果删掉的不是最后一个数,就不管它;

假如我们需要删除 \(x\),首先将 \(x\) 的贡献清空;而 \(x+1\) ~ \(m\)\(pre,sum\) 值就需要相应的变成 \(sum-pre, pre\)

懒标记就直接减一即可

由于懒标记可能为负,我们还要将斐波那契数列反方向扩展,计算方式为:

\[f[-i]=f[-i+2]-f[-i+1],~~i\ge0 \]


代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
namespace MOD
{
    int mod;
    inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
    inline int mul(int a, int b) {return 1ll * a * b % mod;}
    inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
} using namespace MOD;
int n, m, q, a[30005], b[30005], fac[60005];
struct que
{
    int l, r, id;
}t[30005]; int ans[30005];
int B, pos[30005];
inline bool cmp(que a, que b)
{
    return pos[a.l] ^ pos[b.l] ? a.l < b.l : (pos[a.l] & 1 ? a.r < b.r : a.r > b.r);
}
#define ls (now << 1)
#define rs ((now << 1) | 1)
struct Tree
{
    int pre, sum, tag, cnt;
}tr[120005];
inline void Push(int now, int x)
{
    int npre = add(mul(tr[now].pre, fac[m + x - 1]), mul(tr[now].sum, fac[m + x]));
    int nsum = add(mul(tr[now].pre, fac[m + x]), mul(tr[now].sum, fac[m + x + 1]));
    tr[now].pre = npre, tr[now].sum = nsum;
    tr[now].tag += x;
}
inline void down(int now)
{
    if(tr[now].tag)
    {
        Push(ls, tr[now].tag);
        Push(rs, tr[now].tag);
        tr[now].tag = 0;
    }
}
inline void up(int now)
{
    tr[now].pre = add(tr[ls].pre, tr[rs].pre);
    tr[now].sum = add(tr[ls].sum, tr[rs].sum);
    tr[now].cnt = tr[ls].cnt + tr[rs].cnt;
}
void modify_add(int now, int l, int r, int to, int rk)
{
    if(l == r)
    {
        tr[now].pre = mul(fac[m + rk], b[l]);
        tr[now].sum = mul(fac[m + rk + 1], b[l]);
        tr[now].cnt = 1;
        return;
    }
    down(now);
    int mid = (l + r) >> 1;
    if(to <= mid) modify_add(ls, l, mid, to, rk), Push(rs, 1);
    else modify_add(rs, mid + 1, r, to, rk + tr[ls].cnt);
    up(now);
}
void modify_del(int now, int l, int r, int to)
{
    if(l == r)
    {
        tr[now].pre = tr[now].sum = tr[now].cnt = 0;
        return;
    }
    down(now);
    int mid = (l + r) >> 1;
    if(to <= mid) modify_del(ls, l, mid, to), Push(rs, -1);
    else modify_del(rs, mid + 1, r, to);
    up(now);
}
int ncnt[30005];
inline void ADD(int x)
{
    if(!ncnt[a[x]]) modify_add(1, 1, m, a[x], 0);
    ncnt[a[x]]++;
}
inline void DEL(int x)
{
    ncnt[a[x]]--;
    if(!ncnt[a[x]]) modify_del(1, 1, m, a[x]);
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads(), mod = reads(), B = sqrt(n);
    FOR(i, 1, n) a[i] = b[i] = reads(), pos[i] = (i - 1) / B + 1;
    std::sort(b + 1, b + 1 + n);
    m = std::unique(b + 1, b + 1 + n) - b - 1;
    FOR(i, 1, n) a[i] = std::lower_bound(b + 1, b + 1 + m, a[i]) - b;
    FOR(i, 1, m) b[i] %= mod;

    fac[m + 1] = fac[m + 2] = 1;
    FOR(i, m + 3, m << 1) fac[i] = add(fac[i - 1], fac[i - 2]);
    ROF(i, m, 1) fac[i] = sub(fac[i + 2], fac[i + 1]);

    q = reads();
    FOR(i, 1, q) t[i] = (que){reads(), reads(), i};
    std::sort(t + 1, t + 1 + q, cmp);
    int l = 1, r = 0;
    FOR(i, 1, q)
    {
        while(r < t[i].r) ADD(++r);
        while(r > t[i].r) DEL(r--);
        while(l > t[i].l) ADD(--l);
        while(l < t[i].l) DEL(l++);
        ans[t[i].id] = tr[1].sum;
    }
    FOR(i, 1, q) printf("%d\n", ans[i]);
    return 0;
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号