[洛谷 6477][NOI Online #2 提高组]子序列问题

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据