算法

【题解】P6477 [NOI Online t2 提高组]子序列问题

t1炸了

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

暴力优化

最暴力的做法即为枚举每一对 $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$ 的线段树来算出。

最终做法

伪代码：

1
2
3
4
5
6
7

计算出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

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#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. 线段树数组大小