我在观看一个思想前卫的艺术。

· · 题解

我在观看一个思想前卫的代码实现艺术。

如果你翻提交记录你会发现这个题中几乎都写 3K 以上，接下来我们来详细揭秘如何在 2.4K 以内结束战斗。

（实际上本篇题解是对另一篇题解的阐释和进一步的详细说明）

首先如果你是 CQYC 的，并且打了某个八字 id 的人出的邀请赛，那么你会知道有个东西叫齐肯多夫定理。

他保证了任何一个数都可以表示成若干个不相邻不重复的斐波那契数的和。

接下来我们分为两条线：如何在知道表示方法的情况下求出答案，如何在加一个斐波那契数后维护出新的表示方法。

如何在知道表示方法的情况下求出答案

我们知道表示方法后，我们发现，我们只能将表示中的一个 i 拆成 i-1,i-2，而不能往较大的 i 合了。

我们先手玩一下：

0000001

你会发现他会有：

0000110

0011010

1101010

这三种情况。

我们记上一个 1 的位置为 x，这一个 1 的位置为 i，那么我们有 \left \lfloor\frac{i-x-1}{2}\right \rfloor 种拆分方法，当然还有不拆分的 1 种。

更厉害的是，上一个 1 的位置只有两种。

因此这启发我们考虑 dp，记 f_{i,0/1} 为目前考虑到第 i 个 1，它没被拆分/被拆分的方案数。

记第 i 个 1 在 x_i 可以列出转移：

\begin{cases} f_{i,0}=f_{i-1,0}+f_{i-1,1}\\ f_{i,1}=\left\lfloor\frac{x_i-x_{i-1}-1}2\right\rfloor f_{i-1,0}+\left\lfloor\frac{x_i-x_{i-1}}{2}\right\rfloor f_{i-1,1} \end{cases}

如何在加一个斐波那契数后维护出新的表示方法

首先，我们发现这个转移很矩阵，所以最后维护肯定有个数据结构状物。

我们将插入分为三类情况：

先忽略第二种情况。

观察到：每次转移的系数只和上一个 1 的位置有关。

首先第一种情况是简单的，直接插入后寻找前驱后继一下，即可。

对于第三种情况，我们发现：

01010101010

直接变成了：

11010101010

然后：

00000000001

你发现我们不能直接维护每个 1 了（实际上在这里还是可以的，可以通过均摊得到一个正确的复杂度）。

我们考虑维护所有的 1010101010101 形态的 01 段，即可。

一般来讲剩余的一堆东西需要让读者自己去推，但是这太缺德了，我们来讨论如何优雅的实现这一切。

讨？！讨！？

这个题的主要难点在这里，你信吗？你可能会发现这份代码和某篇题解没啥差别，不用乱猜就是在这个基础上阐释的。

接下来考虑如何在这种情况下不写平衡树来维护这一切。

我们要在第一次做中得到要使用的位置，然后离散化所有位置使得第二次可以用线段树维护答案。

为了方便一点，我们就直接说第二次的过程。

我们需要记录一个 map 和一个单修全局查的线段树。

我们要干的事情是，在 map 中记录所有 {l,r} 的 pair，表示 [l,r] 是极长的 10101010101 的段。

然后再线段树的每一个 l 结点，它的权为 [l,r] 的所有 1 的转移矩阵之积，其余的叶子节点都是单位矩阵。

我们要是能高效维护 map，只要在修改 map 的同时，将后继的修改结点更新一下就可以完成线段树。

void update(map<int,int>::iterator it){
    if(it==mp.end())return;
    modify(it->first,/*对应的转移矩阵*/);
}

大概长这样，对应的转移矩阵可以简单通过这一段的长度和上一段与这一段的距离简单求出。

然后我们来处理下 map，维护。

然后我们来分讨：

假设我们要扔一个 i 进去。

i-1,i,i+1 都是 0

首先查一下 map 中最大的 [l,r] 满足 l\le i。

若 r\le i-2 就是这种情况。

然后我们查询关于 i 的前驱后继区间，看 i-2,i+2 是不是 1，如果有就将这些段合并为一段。

int l=x,r=x;
        if(it!=mp.begin()&&prev(it)->second==x-2)l=prev(it)->first,change(l,x-2);
        if(it!=mp.end()&&it->first==x+2)r=it->second,change(x+2,r);
        change(l,r);

其中 change，是一个有 [l,r] 就删除，没有就添加的函数。

i-1,i+1 有一个是 1

下面提及的 [l,r] 是上文所述的 map 中最大的 [l,r] 满足 l\le i，第三种情况亦是如此。

首先 [l,r] 要断成两半了。

比如这时 [l,r]：

10101011101

它变成了：

10101010001。

好像可以再插一个 [l,i-1] 进去，然后再插一个 r+1。

但是如果 i=r+1 呢？上面的逻辑就失效了。

这时你要扔一个 [l,r-2] 和 i+1 回去。

合并两种情况，你能写出：

change(l,min(x-1,r-2));
insert(max(x+1,r+1));

i 是 1

我很难想象这到底是如何写那么简单的。

首先我们会根据 2F_u=F_{u-2}+F_{u+1}。

但是如果你这样分裂一下，然后重新插两个进去，你就会 TLE，因为它重新插入后的 u-2，可能继续插东西。

先这样插回去一个 u+1，你会发现，[l,r] 的后半段直接变成一个 r+1 了。

然后插回去的 u-2 呢？

我们手动模拟一下：

0000101020

变成：

0000102110

接着一直展开，变成了：

0000211110

又一次地，我们发现合成之后得到：

0010010101

我们只要插一个 l-2，和 [l+1,i-1] 就可以了。

然而，你会发现，如果 l=1 或 l=2 会有些特殊情况。

其中 l=1 的情况是不插入 l-2 了。

而 l=2 的情况是无法插入 l-2，我们改插一个 1。

结合一下，可以写出：

change(l+1,x-1);
if(l>1)insert(max(1,l-2));
insert(r+1);

最终实现

只要将上述几段代码拼在一起，然后用你喜欢的方式实现线段树就可以啦。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct Mat{
    long long a,b,c,d;
    Mat operator*(Mat p){
        return {
            (a*p.a+b*p.c)%mod,
            (a*p.b+b*p.d)%mod,
            (c*p.a+d*p.c)%mod,
            (c*p.b+d*p.d)%mod};
    }
};
struct node{
    int l,r;
    Mat s;
}v[4000005];
map<int,int>mp;
int n,op;
int leaf[4000005],a[100005],num[4000005],tot;

void build(int rt,int l,int r){
    v[rt].l=l;v[rt].r=r;v[rt].s={1,0,0,1};
    if(l==r){
        leaf[l]=rt;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
}

void modify(int x,Mat y){
    if(op==0){num[++tot]=x;return;}
    int p=lower_bound(num+1,num+tot+1,x)-num;
    int rt=leaf[p];
    v[rt].s=y;
    rt>>=1;
    while(rt){
        v[rt].s=v[rt<<1|1].s*v[rt<<1].s;
        rt>>=1;
    }
}

Mat get(int len,int cnt){
    long long d1=((len-1)>>1)%mod,d2=(len>>1)%mod;
    return {(d1*(cnt-1)+1)%mod,(d2*(cnt-1)+1)%mod,d1,d2};
}

void update(map<int,int>::iterator it){
    if(it==mp.end())return;
    int l=it->first,r=it->second,lst=(it==mp.begin())? 0:(prev(it)->second);
    modify(l,get(l-lst,(r-l+2)>>1));
}

void change(int l,int r){
    if(l>r)return;
    auto it=mp.lower_bound(l);
    if(it!=mp.end() && it->first==l){
        modify(l,{1,0,0,1});
        it=mp.erase(it);
    }else{
        it=mp.insert({l,r}).first;
        update(it++);
    }
    update(it);
}

void insert(int x){
    auto it=mp.upper_bound(x+1);
    if(it!=mp.begin() &&prev(it)->second>=x-1){
        it--;
        int l=it->first,r=it->second;
        change(l,r);
        if((x-l)&1){
            change(l,min(x-1,r-2));
            insert(max(x+1,r+1));
        }else{
            change(l+1,x-1);
            if(l>1)insert(max(1,l-2));
            insert(r+1);
        }
    }else{
        int l=x,r=x;
        if(it!=mp.begin()&&prev(it)->second==x-2)l=prev(it)->first,change(l,x-2);
        if(it!=mp.end()&&it->first==x+2)r=it->second,change(x+2,r);
        change(l,r);
    }
}

int main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)insert(a[i]);

    sort(num+1,num+tot+1);tot=unique(num+1,num+tot+1)-num-1;op=1;
    build(1,1,tot);
    mp.clear();

    for(int i=1;i<=n;i++){
        insert(a[i]);
        cout<<(v[1].s.a+v[1].s.c)%mod<<'\n';
    }
    return 0;
}

::::