首页 > 其他分享 >CF633H Fibonacci-ish II

CF633H Fibonacci-ish II

时间:2022-09-03 07:33:22浏览次数:87  
标签:pre 30005 int sum II CF633H ish include mod

传送门


思路

考虑使用莫队

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

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

为了方便修改,线段树上需要记录的是:它的排名减一的斐波那契数与它的乘积,以及它的排名的斐波那契数与它的乘积,记为 \(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;
}

标签:pre,30005,int,sum,II,CF633H,ish,include,mod
From: https://www.cnblogs.com/zuytong/p/16651879.html

相关文章

  • CF diary II
    每\(10\)题一篇\(\texttt{>o<}\)。似乎不只有cf\(\texttt{Difficulty:}\)题意题解代码viewcode......
  • GIT克隆项目出现:The authenticity of host ‘gitee.com (xxx.xxx.xxx.xxx)‘ can‘t b
    新生成密钥的时候,gitclone或者push的时候,可能会报这样的错误: Google之后明白,文件夹内少了一个known_hosts文件,本来密钥文件应该是三个,现在只有两个,便报了这样的错误,此......
  • 螺旋矩阵 II
    螺旋矩阵II给你一个正整数n,生成一个包含1到n2所有元素,且元素按顺时针顺序螺旋排列的nxn正方形矩阵matrix。示例1:输入:n=3输出:[[1,2,3],[8,9,4],[7,6,5]......
  • 113.path-sum-ii 路径总和 II
    #include<vector>usingstd::vector;classSolution{private:voidget_sum(TreeNode*root,vector<int>path,intsum,vector<vector<int>>&res,inttarg......
  • Geopandas III (Kafka-Stream)
    GeopandasIII(Kafka-Stream)大家好,在本文中,我们将使用geopandas和matplotlib以及来自kafka的数据制作如下实时地图。文章中使用的代码和数据关联您可以通过访......
  • CF1720E. Misha and Paintings
    题意给出n*n的矩阵,ai,j∈[1,n*n],现在要矩形覆盖若干次,每次把一个正方形的ai,j改为x,求最少的次数使得最后有k种不同的数n<=500题解设sum为初始不同的数,若sum<k则显然只......
  • IIC协议介绍
    讲解I2C协议之前,首先列出GPIO的输出模式配置图,输出模式有推挽输出、开漏输出。推挽输出:可以输出高、低电平,连接数字器件。推挽结果一般是指两个三极管分别受两互补信号的......
  • [Google] LeetCode 150 Evaluate Reverse Polish Notation
    EvaluatethevalueofanarithmeticexpressioninReversePolishNotation.Validoperatorsare+,-,*,and/.Eachoperandmaybeanintegeroranotherexpres......
  • 在博客园的博客文章中自动播放 asciinema
    需求我的文章中都是用Markdown写的,所以嵌入的asciinema只能通过Embedimagelink的方式,这就导致打开文章页面后只有一个asciinema的预览图,点击图片后会跳转到asc......
  • [Google] LeetCode 552 Student Attendance Record II
    Anattendancerecordforastudentcanberepresentedasastringwhereeachcharactersignifieswhetherthestudentwasabsent,late,orpresentonthatday.......