Week2总结——分块/莫队 & 矩阵乘法
1. 分块基本思想
将一个序列分为长度相等（除最后一块）的小块进行处理。
仿照线段树的 lazy 思想，将每一块须处理的信息暂存在 lazy 中。
设块数为 \(S\) ，则第 \(x\) 块的左端点为 \(s(x-1)+1\) , 右端点为 \(sx\) 。
\(x\) 属于第 \((x-1)/s+1\) 块。
一般来说，\(S=\sqrt{n}\) 时，分块处理速度最快，效果最好。
例：若需对长度为 \(n\) 的数列中 \([l,r]\) 的子序列进行处理，可以将 \([l,r]\) 分为三段。
令 \(b_i\) 为 \(i\) 所在的块的编号。
- 对 \([l,s\times b_l]\) 进行暴力处理。 时间复杂度 \(O(S)\) 。
- 对 \([(b_r-1)s+1,r]\) 进行暴力处理。时间复杂度 \(O(S)\) 。
- 对 \([b_l+1,b_r-1]\) 进行处理 。可以将修改信息暂存至 \(lazy\) 数组中，查询时将其下放。时间复杂度 \(O(s)\) 。
伪代码如下：
s = sqrt(n);
void change(int l,int r,int v){
int bx = (x - 1) / s + 1;
int by = (y - 1) / s + 1;
if(bx == by)for(int i = l; i <= r; i++) a[i] += v, return;
for(int i = l; i <= s * bx; i++)a[i] += v;
for(int i = (by - 1) * s + 1; i <= r; i ++)a[i] += v;
for(int i = bx + 1; i <= by - 1; i++)lazy[i]++;
}
void query(int l,int r){
int res;
for(l -> blockL.end)res += a[i];
for(blockr.begin -> r)res += a[i];
for(bl + 1 -> rl - 1)res += sum[i] + lazy[i];//sum[i] 为预处理好的每块元素之和
return res;
}
2.莫队算法
由区间为 \([l,r]\) 的答案扩展至 \([l\pm1,r\pm1]\) 的答案。时间复杂度 \(O(1)\) 。
将询问离线后排序。以询问左端点所在的块的编号作为第一关键字，以询问的右端点作为第二关键字。
bool cmp(ask a,ask b){
int ax = (a.l - 1) / s + 1;
int bx = (b.l - 1) / s + 1;
return ax == bx ? a.r < b.r : ax < bx;
}
代码如下：
void add(ll x) {
tot += cnt[x]++;
}
void del(ll x) {
tot -= --cnt[x];
}
void solve() {
ll l = 1, r = 0;
for(int i = 1; i <= m; i++) {
while(l > ask[i].l)add(a[--l]);
while(r < ask[i].r)add(a[++r]);
while(l < ask[i].l)del(a[l++]);
while(r > ask[i].r)del(a[r--]);
ans[ask[i].id] = tot;
}
}
莫队的修改操作
给莫队加上一个时间戳，即将询问 \([l,r]\) 转换为 \([l,r,time]\) 。
排序的第三关键字是时间戳。
增加了一个元素，所以将块长变为 \(n^{2/3}\) ，分成 \(n^{1/3}\) 块。
代码如下：
for(int i = 1; i <= m; i++) {
char op;
int x, y;
cin >> op >> x >> y;
if(op == 'Q') {
askcnt++;
ask[askcnt].l = x, ask[askcnt].r = y;
ask[askcnt].id = askcnt;
ask[askcnt].time = j;
} else {
j++;
change[j].p = x, change[j].nw = y;
change[j].od = a[x];
a[x] = y;
}
}
for(int i = 1, Q = 1; i <= n; i++)
bck[i] = Q, Q += i % s == 0 ? 1 : 0;
sort(ask + 1, ask + askcnt + 1, cmp);
for(int i = 1; i <= askcnt; i++) {
while(L < ask[i].l)del(L++);
while(L > ask[i].l)add(--L);
while(R < ask[i].r)add(++R);
while(R > ask[i].r)del(R--);
while(T > ask[i].time)modify(change[T].p, change[T--].od);
while(T < ask[i].time)modify(change[++T].p, change[T].nw);
ans[ask[i].id] = tot;
}
3.矩阵乘法
运算规则：
即：若 \(A\) 为 \(x\) 行 \(y\) 列的矩阵，\(B\) 为 \(y\) 行 \(z\) 列的矩阵， \(C=A\times B\)
则有 \(C_{i,j}=\sum_{k=1}^yA_{i,k}B_{k,j}\) 。
矩阵乘法计算递推式
若有递推式形如 \(A_n=\sum_{i=1}^n\sum_{j=1}^mT_jA_i+p\)，则可以用矩阵乘法进行优化。
例：对于斐波拉契数列，有 \(F_n=F_{n-1}+F_{n-2}\) 。
问题可以转换为：有矩阵 \(A\) ，使得\(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times A=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\)。
则有 \(\begin{bmatrix}F_{n-1}&F_{n-2}\end{bmatrix}\times A=\begin{bmatrix}F_{n-1}+F_{n-2}&F_{n-1}\end{bmatrix}\) 。
易构造出 \(A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\) 。
故有 \(\begin{bmatrix}F_{2}&F_{1}\end{bmatrix}\times A^{n-1}=\begin{bmatrix}F_{n}&F_{n-1}\end{bmatrix}\) 。
\(A^{n-1}\) 可以用快速幂进行计算，时间复杂度 \(O(log_n)\) 。
代码封装如下：
struct arr {
int c[maxSize + 5][maxSize + 5];
arr() {
memset(c, 0, sizeof c);
}
clear() {
memset(c, 0, sizeof c);
}
void operator = (const int b[maxSize][maxSize]) {
for(int i = 1; i <= maxSize; i++)
for(int j = 1; j <= maxSize; j++)
c[i][j] = b[i][j];
}
arr operator * (const arr& b) const {
arr res;
int r;
for(int i = 1; i <= maxSize; i++) {
for(int k = 1; k <= maxSize; k++) {
r = c[i][k];
for(int j = 1; j <= maxSize; j++) {
res.c[i][j] += b.c[k][j] * r % mod, res.c[i][j] %= mod;
}
}
}
return res;
}
arr operator % (int b) const {
arr res;
if(b == 0)return res;
for(int i = 1; i <= maxSize; i++)
for(int j = 1; j <= maxSize; j++)
res.c[i][j] = c[i][j] % b;
return res;
}
arr operator + (const arr& b) const {
arr res;
for(int i = 1; i <= maxSize; i++)
for(int j = 1; j <= maxSize; j++)
res.c[i][j] = c[i][j] + b.c[i][j], res.c[i][j] %= mod;
return res;
}
arr operator ^ (int b) const {
arr res, bas;
for(int i = 1; i <= maxSize; i++)res.c[i][i] = 1;
for(int i = 1; i <= maxSize; i++)
for(int j = 1; j <= maxSize; j++)
bas.c[i][j] = c[i][j] % mod;
while(b > 0) {
if(b & 1)res = res * bas % mod;
bas = bas * bas % mod;
b >>= 1;
}
return res;
}
};
——\(By\) \(CQWDX\)
\(July\) \(16_{th}\)