目录
显示
题目链接
https://www.luogu.com.cn/problem/P6477
题解
值域很大，先离散化。
接下来考虑一个个地向序列中添加元素。
假如我们现在准备添加第 \(r\) 个元素，对于右端点不是 \(r\) 的区间显然没有影响，对于右端点是 \(r\) 的区间，我们显然可以这样计算 \(f\)：
$$f(l,r)=f(l,r-1)+[a_r \notin \{a_l,\ldots,a_{r-1}\}]$$
容易发现，使得 \(a_r \notin \{a_l,\ldots,a_{r-1}\}\) 成立的 \(l\) 一定是一个连续的区间。
设 \(a_i\) 的值上一次出现的位置为 \(last_i\)，显然，对于每个 \(r\)，使得 \(a_r \notin \{a_l,\ldots,a_{r-1}\}\) 成立的 \(l\) 的范围是 \([last_r+1,r]\)。
这样我们就可以用数据结构维护 \(f(l,r)\) 的值了。每次插入一个新元素时，我们根据上面的式子更新 \(f\) 的值，并累加 \(\sum_{l=1}^r f(l,r)\) 到答案中即可。
现在问题来了，我们要求的是 \(f(l,r)\) 的平方和，这个该如何处理？
$$\begin{align} \sum (x+y)^2 &= \sum x^2+2xy+y^2\\ &=\sum x^2 + 2y \sum x + y^2 \end{align}$$
根据上式，我们需要维护 \(f(l,r)^2\) 和 \(f(l,r)\) 这两个信息，利用 \(f(l,r)\) 来更新 \(f(l,r)^2\) 即可。
（\(10^6\) 用线段树维护可能会被卡，用树状数组效率会高不少）
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int a[1000005],b[1000005],c[1000005],last[1000005];
struct seg
{
long long sum,sum2,tag;
}s[4000005];
void pushup(int root)
{
s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
s[root].sum2=(s[root<<1].sum2+s[root<<1|1].sum2)%MOD;
}
void pushdown(int root,int l,int r)
{
long long tag=s[root].tag;
int ls=root<<1,rs=root<<1|1,mid=(l+r)>>1;
s[ls].sum2=(s[ls].sum2+2*s[ls].sum*tag+(mid-l+1)*tag%MOD*tag)%MOD;
s[rs].sum2=(s[rs].sum2+2*s[rs].sum*tag+(r-mid)*tag%MOD*tag)%MOD;
s[ls].sum=(s[ls].sum+(mid-l+1)*tag)%MOD;
s[rs].sum=(s[rs].sum+(r-mid)*tag)%MOD;
s[ls].tag+=tag;
s[rs].tag+=tag;
s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
if(cr<l||r<cl)return;
if(l<=cl&&cr<=r)
{
s[root].sum2=(s[root].sum2+2*s[root].sum+(cr-cl+1))%MOD;
s[root].sum=(s[root].sum+(cr-cl+1))%MOD;
s[root].tag++;
return;
}
pushdown(root,cl,cr);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r);
update(root<<1|1,mid+1,cr,l,r);
pushup(root);
}
int main()
{
ios::sync_with_stdio(false);
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>b[i];
c[i]=b[i];
}
sort(b+1,b+n+1);
int l=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+l+1,c[i])-b;
update(1,1,n,last[a[i]]+1,i);
ans=(ans+s[1].sum2)%MOD;
last[a[i]]=i;
}
cout<<ans<<endl;
return 0;
}