P6477子序列问题 题解

· · 题解

本文latex在博客中没挂，请在博客页面查看点这里

注：本题解看似很长其实是非常详细，实则思路简单粗暴，容易理解

暴力优化

最暴力的做法即为枚举每一对 l，r，并分别计算其 f(l,r) 的值。但这样不知道会慢到哪里去了，所以我们考虑只滚动 l 的值，并每次计算 G(l)=\sum_{r=l}^{n} f^2(l,r) 的值。

转移

考虑 G(l) 如何从 G(l-1) 转移过来，由 G 的定义：

\begin{aligned} G(l-1)&=&f^2(l-1,l-1)+&f^2(l-1,l)&&+\cdots +f^2(l-1,n)\cr G(l)&=&&f^2(l,l)&&+\cdots +f^2(l,n) \end{aligned}

不难发现，G(l) 与 G(l-1) 的唯一区别在于 G(l) 中的每个 f(l,i) 的值都少考虑了 A_{l-1}，即：

\begin{aligned} f(l-1,l-1)&\rightarrow0\cr f(l-1,l)&\rightarrow f(l,l)\cr f(l-1,l+1)&\rightarrow f(l,l+1)\cr f(l-1,l+2)&\rightarrow f(l,l+2)\cr &\vdots \end{aligned}

（f(l-1,l-1) 彻底没了）。

所以为了计算 A_{l-1} 对哪些 f 有影响，我们可以先预处理出一个数组 suf[i]，表示 A_x=A_i 且 x>i 时，x 的最小值（如果找不到这样的数，则 suf[i]=n+1）。

在从 G(l-1) 转移到 G(l) 的过程中，A_{l-1} 的消失只对 f(l-1,l-1\sim suf[l-1]-1) 有影响（会-1）,因为 f(l-1,suf[l-1]\sim n) 中，都有超过两个与 A_{l-1} 相等的元素，所以即使 A_{l-1} 消失了，这些区间内数字的种类数也不会变。

即：

f(l,r)=\left\{ \begin{aligned} &f(l-1,r)+1&&(r\in[l-1,suf[l-1]-1])\cr &f(l-1,r)&&(r\in[suf[l-1],n]) \end{aligned} \right.

这样，我们就可以通过线段树维护 f(l-1,i)，在 \log(n) 的时间内，将每一个 f(l-1,i) 转移成 f(l,i)（区间修改）。

但是这题答案要求的是 f(l,i) 的平方和，怎么办？

由前缀和维护平方和

对于 f(l-1,r) ,如果 f(l,r)=f(l-1,r)-1 那么

\begin{aligned} f^2(l,r)&=(f(l-1,r)-1)^2\cr &=f^2(l-1,r)-(2f(l-1,r)-1) \end{aligned}

又因为

\begin{aligned} G(l-1)-G(l)=(f^2(l-1,l-1)&-0)+\cr (f^2(l-1,l)&-f^2(l,l))+\cr (f^2(l-1,l+1)&-f^2(l,l+1))+\cr &\vdots\cr (f^2(l-1,n)&-f^2(l,n)) \end{aligned}

又因为刚才推出 r\in[suf[l-1],n] 时，f(l-1,r) 与 f(l,r) 相同，所以式子中许多项被消掉了（式子中的 n 变成了 suf[l-1]）

\begin{aligned} G(l-1)-G(l)=(f^2(l-1,l-1)&-0)+\cr (f^2(l-1,l)&-f^2(l,l))+\cr (f^2(l-1,l+1)&-f^2(l,l+1))+\cr &\vdots\cr (f^2(l-1,{\color{red}suf[l-1]-1})&-f^2(l,{\color{red}suf[l-1]-1})) \end{aligned}

又由于第二部分的结论（r\in[l-1,suf[l-1]-1] 时，f(l-1,r)=f(l,r)+1）和这部分开头的结论，式子可以再次化简：

\begin{aligned} G(l)-G(l-1)&=&-(2f(l-1,l-1)&-1)\cr &&-(2f(l-1,l)&-1)\cr &&-(2f(l-1,l+1)&-1)\cr &&&\vdots\cr &&-(2f(l-1,suf[l-1]-1)&-1)\cr &=&-2\times\sum_{r=l-1}^n f(l-1,r)+((suf[l-1])&-(l-1)+1) \end{aligned}

这个值可以直接用刚才维护 f 的线段树来算出。

最终做法

伪代码：

计算出f(1,1)~f(1,n)的值，建线段树
tot=G(1)
ans=0
for l in [1,n]:
    ans+=tot;
    tot+=G(l+1)-G(l) (通过线段树计算)
    将 f(l,l)~f(l,suf[l]-1) 减1

最终代码：（除去线段树极其简短）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const long long P=1000000007;
const long long MXN=1e6+5;
long long n;
long long arr[MXN],pool[MXN];
long long suf[MXN],nxt[MXN],diff[MXN];
long long tot=0,ans=0;

//线段树
struct stree{
    long long t[MXN<<2],tag[MXN<<2];
    inline long long ls(long long p){return p<<1;}
    inline long long rs(long long p){return (p<<1)|1;}
    inline void push_up(long long p){t[p]=t[ls(p)]+t[rs(p)];}
    inline void add_tag(long long p,long long l,long long r,long long k){
        tag[p]+=k;
        t[p]+=k*(r-l+1);
    }
    inline void push_down(long long p,long long l,long long r){
        if(!tag[p])return;
        long long mid=(l+r)>>1;
        add_tag(ls(p),l,mid,tag[p]);
        add_tag(rs(p),mid+1,r,tag[p]);
        tag[p]=0;
    }
    void build(long long p,long long l,long long r){
        tag[p]=0;
        if(l==r){
            t[p]=diff[l];
            return;
        }
        long long mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);
    }
    void mo(long long p,long long l,long long r,long long al,long long ar,long long k){
        //区间是否合法
        if(al>ar)return;
        if(al<=l && r<=ar){
            add_tag(p,l,r,k);
            return;
        }
        long long mid=(l+r)>>1;
        push_down(p,l,r);
        if(al<=mid)mo(ls(p),l,mid,al,ar,k);
        if(ar>mid)mo(rs(p),mid+1,r,al,ar,k);
        push_up(p);
    }
    long long query(long long p,long long l,long long r,long long al,long long ar){
        //区间是否合法
        if(al>ar)return 0;
        if(al<=l && r<=ar)return t[p];
        long long mid=(l+r)>>1;
        push_down(p,l,r);
        long long res=0;
        if(al<=mid)res+=query(ls(p),l,mid,al,ar);
        if(ar>mid)res+=query(rs(p),mid+1,r,al,ar);
        return res;
    }

}tree;
void init(){
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",arr+i);
        pool[i]=arr[i];
        nxt[i]=n+1;
    }
    //离散化
    sort(pool+1,pool+1+n);
    long long cnt=unique(pool+1,pool+1+n)-pool-1;
    for(long long i=1;i<=n;i++)
        arr[i]=lower_bound(pool+1,pool+1+cnt,arr[i])-pool;
    //计算suf[i]
    for(long long i=n;i>=1;i--){
        suf[i]=nxt[arr[i]];
        nxt[arr[i]]=i;
    }
    //计算f(1,1)~f(1,n)
    memset(pool,0,sizeof(pool));
    for(long long i=1;i<=n;i++){
        diff[i]=diff[i-1];
        diff[i]+=((pool[arr[i]]++)==0);
        tot+=diff[i]*diff[i];
        tot%=P;
    }
    //建树
    tree.build(1,1,n);
}
void solve(){
    for(long long i=1;i<=n;i++){
        ans+=tot;
        ans%=P;
        tot-=(tree.query(1,1,n,i,suf[i]-1)*2)-(suf[i]-i);
        tot%=P;
        tree.mo(1,1,n,i+1,suf[i]-1,-1);
    }
}
int main(){
    /*freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);*/
    init();
    solve();
    ans%=P;
    if(ans<0)ans+=P;
    printf("%lld",ans);

    return 0;
}

易错点

  1. 随时%p，如果不开 long long 小心越界
  2. 计算 suf[i] 的时候如果用类似桶排序的方法要离散化
  3. 线段树中查询和修改操作要判断查询的区间是否合法，如果否，要直接退出（本题解中，为了写得更加方便，suf[i] 的定义比较特别（如果找不到这样的数，则 suf[i]=n+1），所以如果不特判可能会re）
  4. 线段树数组大小