OI - Fibonacci-ish II(Codeforces)

线段树专题训练继续……了解到一个线段树存储矩阵的操作~


Part1. 题目

> codeforces 633H 传送门

给出一个长度为 $n$ 的序列 $a_i$ 和一个整数 $mod$。

有 $m$ 次操作,每次操作给出区间 $[l,r]$:将 $a_l,a_{l+1}…a_r$ 从小到大排序、去重后得到序列 $b_1,b_2,…,b_k$,计算 $\sum_{i=1}^kb_i\times f_i$(其中 $f_i$ 是斐波那契数第 $i$ 项,$f_0=0,f_1=f_2=1$)。

(每次操作独立,即每次操作互不影响)

数据规模:$1\leq n,m,mod\leq30000$,$0\leq a_i\leq10^9$,$1\leq l\leq r\leq n$。


Part2. 解析

区间操作,$n\leq30000$……似乎 $O(n\sqrt n)$ 能过?于是想到可以莫队。

Part2/1. 莫队

先把 $a_i$ 离散化,然后 $a_i$ 就小于等于 $n$ 了。维护一个 cnt[i] 表示在当前区间(因为莫队其实是滑窗嘛)中数 i 出现的次数:这样如果收缩区间时数 i 出去了,就 cnt[i]--,如果扩大区间时 i 进入了区间,就 cnt[i]++

于是我们可以知道:

  1. 当数 i 进入区间时,如果 i 之前没有在 $b_i$ 中,就把 i 插入 $b_i$(这样相当于去重);
  2. 当数 i 离开区间时,如果删除 i 后,区间中没有 i 了,就在 $b_i$ 中删去 i

那么我们就需要一个数据结构,来维护 $b_i$。

Part2/2. 矩阵

对于斐波那契数列,有一个广为人知的矩阵递推式:

显然下式也成立:

又因为矩阵乘法的分配律 $A(B+C)=AB+AC$。可以得到下式:

Part2/3. 权值线段树

Part2/3/1. 维护节点信息

对于权值线段树维护的一个区间 $[l,r]$:设序列 $B_{l,r}=\{b_i | l\leq b_i\leq r\}$,则区间 $[l,r]$ 里存储的是:

  1. $S_{l,r}$,$B_{l,r}$ 的大小;
  2. 一个矩阵 $M_{l,r}=\begin{bmatrix}\sum_{i=1}{B_{l,r}}[i]\times f_i\\\sum_{i=1}B_{l,r}[i]\times f_{i-1}\end{bmatrix}$,其中 $B_{l,r}[i]$ 指 $B_{l,r}[i]$ 中的第 $i$ 个元素。

那么对于一个线段树的节点 $[l,r]$ ,它的左儿子 $[l,m]$ 和右儿子 $[m+1,r]$ 可以这样合并起来:

(应该比较直观吧)

这样的话,我们可以预处理出 $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{k}$ ,然后就可以在常数时间(矩阵乘法的常数时间)内合并两个区间了~

Part2/3/2. 插入/删除元素

设插入元素 $i$:

我们就在线段树的区间 $[i,i]$ 处,将 $S_{i,i}$ 修改为 $1$,并且把 $M_{i,i}$ 修改为 $\begin{bmatrix}i\\0\end{bmatrix}$,然后向上更新节点信息直到根节点。

如果删除元素 $i$:

就把 $S_{i,i}$ 改为 $0$,$M_{i,i}$ 改为 $\begin{bmatrix}0\\0\end{bmatrix}$,向上更新节点信息即可。

Part2/3/3. 答案

最后根节点的信息就是当前整个序列的信息,即:

那么 $\sum_{i=1}b_i\times f_i$ 即是答案。


Part3. 源代码

注意取模是非常慢的……可以用减法代替取模,速度大概会快这么多:

png1

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/*Lucky_Glass*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e4;

int n,m,Vper,Nl,Nr,Vmod,Vlim;
int Ia[N+3],Ecnt[N+3],Eans[N+3];
vector<int> Sra;
struct QUERY{int Cl,Cr,id;}qry[N+3];
struct MATRIX{
int Vrol,Vcol;
int Emat[3][3];
MATRIX operator *(const MATRIX &B)const &{
MATRIX Rr;
Rr.Vrol=Vrol;Rr.Vcol=B.Vcol;
for(int i=1;i<=Rr.Vrol;i++)
for(int j=1;j<=Rr.Vcol;j++){
Rr.Emat[i][j]=0;
for(int k=1;k<=Vcol;k++){
Rr.Emat[i][j]+=1ll*Emat[i][k]*B.Emat[k][j]%Vmod;
if(Rr.Emat[i][j]>=Vmod) Rr.Emat[i][j]-=Vmod;
}
}
return Rr;
}
MATRIX operator +(const MATRIX &B)const &{
MATRIX Rr;
Rr.Vrol=Vrol;Rr.Vcol=Vcol;
for(int i=1;i<=Rr.Vrol;i++)
for(int j=1;j<=Rr.Vcol;j++){
Rr.Emat[i][j]=Emat[i][j]+B.Emat[i][j];
if(Rr.Emat[i][j]>=Vmod) Rr.Emat[i][j]-=Vmod;
}
return Rr;
}
}Mper,Mfeb[N+3];
struct SEGTREE{
int Tnum[N*4];
MATRIX Tmat[N*4];
inline void PushUp(int u){
Tnum[u]=Tnum[u<<1]+Tnum[u<<1|1];
Tmat[u]=Tmat[u<<1]+Mfeb[Tnum[u<<1]]*Tmat[u<<1|1];
}
inline void Build(register int u,register int Vl,register int Vr){
Tmat[u].Vcol=1;Tmat[u].Vrol=2;
if(Vl==Vr) return;
register int Vm=(Vl+Vr)>>1;
Build(u<<1,Vl,Vm);
Build(u<<1|1,Vm+1,Vr);
}
inline void Modify(register int u,register int Vl,register int Vr,register int Upos,register int Utmp){
if(Vl==Vr){
Tmat[u].Emat[1][1]=(Utmp*Sra[Vl-1]%Vmod+Vmod)%Vmod;
Tmat[u].Emat[2][1]=0;
Tnum[u]=Utmp;
return;
}
register int Vm=(Vl+Vr)>>1;
if(Upos<=Vm) Modify(u<<1,Vl,Vm,Upos,Utmp);
else Modify(u<<1|1,Vm+1,Vr,Upos,Utmp);
PushUp(u);
}
}seg;

inline bool cmpQUERY(const QUERY Ca,const QUERY Cb){
register int Ba=Ca.Cl/Vper,Bb=Cb.Cl/Vper;
if(Ba==Bb)
if(Ba&1) return Ca.Cr<Cb.Cr;
else return Ca.Cr>Cb.Cr;
else
return Ca.Cl<Cb.Cl;
}
inline void NAdd(register int Vv){
Ecnt[Ia[Vv]]++;
if(Ecnt[Ia[Vv]]==1)
seg.Modify(1,1,Vlim,Ia[Vv],1);
}
inline void NDelete(register int Vv){
Ecnt[Ia[Vv]]--;
if(Ecnt[Ia[Vv]]==0)
seg.Modify(1,1,Vlim,Ia[Vv],0);
}
void Process(){
Mper.Vcol=Mper.Vrol=2;
Mper.Emat[1][1]=1;Mper.Emat[1][2]=1;
Mper.Emat[2][1]=1;Mper.Emat[2][2]=0;
Mfeb[0].Vcol=Mfeb[0].Vrol=2;
Mfeb[0].Emat[1][1]=1;Mfeb[0].Emat[1][2]=0;
Mfeb[0].Emat[2][1]=0;Mfeb[0].Emat[2][2]=1;
for(register int i=1;i<=n;i++)
Mfeb[i]=Mfeb[i-1]*Mper;
}
inline int fRead(){
register int Vx=0;char Cc=getchar();
while(Cc<'0' || '9'<Cc) Cc=getchar();
while('0'<=Cc && Cc<='9') Vx=(Vx<<3)+(Vx<<1)+Cc-'0',Cc=getchar();
return Vx;
}
int main(){
n=fRead();Vmod=fRead();
Process();
for(register int i=1;i<=n;i++){
Ia[i]=fRead();
Sra.push_back(Ia[i]);
}
m=fRead();
for(register int i=1;i<=m;i++){
qry[i].Cl=fRead();qry[i].Cr=fRead();
qry[i].id=i;
}

sort(Sra.begin(),Sra.end());
Sra.erase(unique(Sra.begin(),Sra.end()),Sra.end());
for(register int i=1;i<=n;i++) Ia[i]=lower_bound(Sra.begin(),Sra.end(),Ia[i])-Sra.begin()+1;

Vper=ceil(sqrt(n));
sort(qry+1,qry+1+m,cmpQUERY);

Vlim=Sra.size();
seg.Build(1,1,Vlim);

Nl=1;
for(register int i=1;i<=m;i++){
while(Nr<qry[i].Cr) NAdd(++Nr);
while(Nr>qry[i].Cr) NDelete(Nr--);
while(Nl<qry[i].Cl) NDelete(Nl++);
while(Nl>qry[i].Cl) NAdd(--Nl);
Eans[qry[i].id]=seg.Tmat[1].Emat[1][1];
}
for(register int i=1;i<=m;i++)
printf("%d\n",Eans[i]);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问~

0%