注:本题解看似很长其实是非常详细,实则思路简单粗暴,容易理解
暴力优化
最暴力的做法即为枚举每一对 \(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)\\ G(l)&=&&f^2(l,l)&&+\cdots +f^2(l,n) \end{aligned}\]不难发现, \(G(l)\) 与 \(G(l-1)\) 的唯一区别在于 \(G(l)\) 中的每个 \(f()\) 的值都少考虑了 \(A_{l-1}\) ,即:
\[\begin{aligned} f(l-1,l-1)&\rightarrow0\\ f(l-1,l)&\rightarrow f(l,l)\\ f(l-1,l+1)&\rightarrow f(l,l+1)\\ f(l-1,l+2)&\rightarrow f(l,l+2)\\ &\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])\\ &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\) 的平方和,怎么办?
由前缀和维护平方和
(推导类似数学归纳法)
对于 \(f(l-1,r)\) ,如果 \(f(l,r)=f(l-1,r)-1\) 那么
\[\begin{aligned} f^2(l,r)&=(f(l-1,r)-1)^2\\ &=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)+\\ (f^2(l-1,l)&-f^2(l,l))+\\ (f^2(l-1,l+1)&-f^2(l,l+1))+\\ &\vdots\\ (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)+\\ (f^2(l-1,l)&-f^2(l,l))+\\ (f^2(l-1,l+1)&-f^2(l,l+1))+\\ &\vdots\\ (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)\\ &&-(2f(l-1,l)&-1)\\ &&-(2f(l-1,l+1)&-1)\\ &&&\vdots\\ &&-(2f(l-1,suf[l-1]-1)&-1)\\ &=&-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;
}
易错点
- 随时%p,如果不开 long long 小心越界
- 计算 \(suf[i]\) 的时候如果用类似桶排序的方法要离散化
- 线段树中查询和修改操作要判断查询的区间是否合法,如果否,要直接退出(本题解中,为了写得更加方便, \(suf[i]\) 的定义比较特别(如果找不到这样的数,则 \(suf[i]=n+1\) ),所以如果不特判可能会re)
- 线段树数组大小
作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接
阅读量: