【题解】Fibonacci-ish II

传送门

题目分析

根据题目范围 \(n\le 30000\) 并且此题可以离线维护这个很恶心的东西，所以我们考虑莫队。由于要求访问到任意一个区间都要求知道它有序之后的序列，所以这个东西可以用权值线段树维护。因此，此题正解是莫队+权值线段树。

我们分类讨论一下加上一个数，删除一个数对答案的影响。

加上一个数相当于它自己的排名乘上对应的斐波那契数列，但在它右边的数乘上的斐波那契数列都要往右移一位。考虑推出知道向右边移 \(c\) 位（可能是负数）之后快速计算新增贡献的式子。也就是知道 \(f[i],f[c]\)，怎么推出 \(f[i+c]\)。

严谨的证明？我不会。但我们可以大胆猜结论。
假设 \(c=1\)，那么显然 \(f[i+1]=f[i]+f[i-1]\)。
假设 \(c=2\)，那么 \(f[i+2]=f[i+1]+f[i]=f[i]+f[i-1]+f[i]=2f[i]+f[i-1]\)。
假设 \(c=3\)，那么 \(f[i+3]=f[i+2]+f[i+1]=2f[i]+f[i-1]+f[i]+f[i-1]=3f[i]+2[i-1]\)。
...
再往下面枚举，或者你感性理解，会发现 \(f[i]\) 和 \(f[i-1]\) 前面的系数也是一个斐波那契数列，手玩一下得出 \(f[i+c]=f[i]\times f[c]+f[i-1]\times f[c-1]\) （斐波那契数列下标从 \(0\) 开始）。

所以对于线段树上的每一个节点，我们维护三个值 \(pre,v\) 表示上一位 \(f[i-1]\) 乘上这个节点的值和现在对应的 \(f[i]\) 乘上这个节点的值。

减去一个数相当于在它右边的数乘上的斐波那契数列都要往左移一位，接下来的处理和加一位一样，只是 \(c\) 为负数了。

实现

莫队是用来处理这个数在当前区间出现了几次，如果不是第一次我们就不用管。

//buc表示这个数出现了几次
inline void add(int x){
    buc[a[x]]++;
    if(buc[a[x]]==1){
        update(1,1,K,a[x],1);
    }
}
inline void del(int x){
    buc[a[x]]--;
    if(buc[a[x]]==0) update(1,1,K,a[x],-1);
}

权值线段树维护的是当前区间的答案。在更改函数中，如果要更改的节点在左子树，那么我们将右子树都打上一个向右/左移一位的标记，如果在右子树那么它对左子树显然是没影响的。更改到叶子节点时，如果是删除操作那么直接赋值为 \(0\)，否则看它要往右移几位再更改。

为什么在叶子节点的赋值是 \(tree[cur].v=b[lt]\times f[K+tag[cur]+1]\)，为什么是懒标记数组？ 我们在右子树打上标记并不是只给现在有权值的节点打上标记，而是给所有节点都打上。显然左边有多少个节点这个节点就会被打上多少次标记，因此可以通过懒标记数组看它目前的排名。

inline void update(int cur,int lt,int rt,int qx,int opt){
//opt表示是向左移还是向右移，也就是opt=-1表示删除，opt=1表示添加
//b数组是离散化后对应的原数组
//K是一个常数，因为可能会往左移，为了防止数组下标为负数而加的
    if(lt==rt){
        if(opt==-1) tree[cur].pre=tree[cur].v=0;
        else{
            tree[cur].pre=1ll*b[lt]*f[K+tag[cur]]%mod;
            tree[cur].v=1ll*b[lt]*f[K+tag[cur]+1]%mod;
        }
        return;
    }
    pushdown(cur);
    int mid=(lt+rt)>>1;
    if(qx<=mid){
        update(cur<<1,lt,mid,qx,opt);
        addtag(cur<<1|1,opt);
    }
    else update(cur<<1|1,mid+1,rt,qx,opt);
    pushup(cur);
}

添上标记的函数直接上之前推的式子即可。

inline void addtag(int cur,int k){
    long long np=(1ll*tree[cur].pre*f[k-1+K]+1ll*tree[cur].v*f[k+K])%mod;
    long long nv=(1ll*tree[cur].pre*f[k+K]+1ll*tree[cur].v*f[k+1+K])%mod;
    tag[cur]+=k;
    tree[cur].pre=np;
    tree[cur].v=nv;
}

预处理斐波那契数列 \(f[i]\)

f[K+1]=f[K+2]=1;
for(int i=K+3;i<=K*2;++i){
	f[i]=f[i-1]+f[i-2];
	if(f[i]>=mod) f[i]-=mod;
	//    cout<<f[i]<<" ";
}
for(int i=K;i>=0;--i){
	f[i]=f[i+2]-f[i+1];
	if(f[i]<0) f[i]+=mod;
}

我们发现实际上的第 \(0\) 项是 \(K+1\)，这就是为什么之前 addtag 函数中要乘上原本 \(+1\) 项的斐波那契数列了。

查询时直接返回 \(tree[1].v\) 即可。

注意本题有点卡常，不建议 #define int long long。

总结

推式子时可以考虑从特殊到一般大胆猜结论。