2022牛客寒假算法基础集训营1
ST表
倍增与二进制划分相结合可以降低很多题目的算法复杂度。主要常见的应用为求区间最值问题(RMQ)的ST表,以及求解最近公共祖先(LCA)的树上倍增思想。
以下总结的关于RMQ问题的思想。
功能
O(1)时间复杂度内在线回答数组中在下标 [ l , r ] [l, r] [l,r]之间的数最大值为多少。但是需要NlogN的时间预处理。
定义
f [ i , j ] : 表示数列 A 中下标在区间 [ i , i + 2 j − 1 ] 里的数的最大值,也就是从 i 开始的 2 j 个数的最大值。 f[i, j] : 表示数列A中下标在区间[i, i + 2^j - 1]里的数的最大值,也就是从i开始的2^j个数的最大值。 f[i,j]:表示数列A中下标在区间[i,i+2j−1]里的数的最大值,也就是从i开始的2j个数的最大值。
递推边界: f [ i , 0 ] = A [ i ] f[i, 0] = A[i] f[i,0]=A[i]
状态转移方程
f [ i , j ] = m a x ( f [ i , j − 1 ] , f [ i + 2 j − 1 , j − 1 ] ) f[i, j] = max(f[i, j - 1], f[i + 2^{j - 1}, j - 1]) f[i,j]=max(f[i,j−1],f[i+2j−1,j−1])
f [ i ] [ j ] = m a x ( f [ i ] [ j − 1 ] , f [ i + ( 1 < < ( j − 1 ) ) ] [ j − 1 ] ) ; f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); f[i][j]=max(f[i][j−1],f[i+(1<<(j−1))][j−1]);
即长度为 2 j 2^j 2j 的的区间的最大值等于左右两个长度为 2 j − 1 2^{j - 1} 2j−1的区间的最大值中较大的一个。
查询
当查询任意区间的最值时,我们需要先计算出一个满足以下条件的k值, 2 k ≤ r − l + 1 < 2 k + 1 2^k \leq r- l + 1 < 2^{k + 1} 2k≤r−l+1<2k+1,也即使2的次幂小于区间长度的同时尽量大的一个k值。
代码
int n; cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) f[i][0] = a[i];int t = log(n) / log(2) + 1;//mp数组记录长度为j的区间对应的k值for (int i = 0; i <= t; i++)for (int j = 1 << i; j < min(n + 1, 1 << (i + 1)); j++)mp[j] = i;for (int j = 1; j < t; j++)for (int i = 1; i <= n - (1 << j) + 1; i++)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);int q; cin >> q;while (q--){int l, r; cin >> l >> r;int k = mp[r - l + 1];cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;}
拓展(二维RMQ问题)
有两种方法
-
f [ i ] [ j ] [ k ] : 以点 ( i , j ) 为左上角坐标,边长为 2 k 的矩阵中的最值 f[i][j][k]: 以点(i, j)为左上角坐标,边长为 2^k 的矩阵中的最值 f[i][j][k]:以点(i,j)为左上角坐标,边长为2k的矩阵中的最值
f [ i ] [ j ] [ k ] = f [ i ] [ j ] [ k − 1 ] + f [ i + ( 1 < < ( k − 1 ) ) ] [ j ] [ k − 1 ] + f [ i ] [ j + ( 1 < < ( k − 1 ) ) ] [ k − 1 ] + f [ i + ( 1 < < ( k − 1 ) ) ] [ j + ( 1 < < ( k − 1 ) ) ] [ k − 1 ] f[i][j][k] = f[i][j][k - 1] +\\ f[i + (1 << (k - 1))][j][k - 1] + \\ f[i][j + (1 << (k - 1))][k - 1] +\\ f[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1] f[i][j][k]=f[i][j][k−1]+f[i+(1<<(k−1))][j][k−1]+f[i][j+(1<<(k−1))][k−1]+f[i+(1<<(k−1))][j+(1<<(k−1))][k−1]类似于二维区间前缀和, 其实就是一个 “田”字, 一次查询即为答案,时间复杂度 O ( 1 ) O(1) O(1) -
f [ i ] [ j ] [ k ] : 第 i 行,区间 [ j , j + 2 k − 1 ] 中的最值 f[i][j][k]:第i行,区间[j, j + 2^k - 1]中的最值 f[i][j][k]:第i行,区间[j,j+2k−1]中的最值
转移方程与一般的ST表一样,只是多了一维。一次查询需要循环k次, 时间复杂度 O ( k ) O(k) O(k)
Solution
很明显,对于模3相等的初始值,其相同区间的分数变化量相同。所以我们只需要分别求出初始值为0, 1, 2时所有子区间各自对应的区间和即可。详细细节见下面的代码。
Code
const int N = 3e5 + 5;
int cnt = 0;
int f[3][N][20];//注意数组越界
int mp[N];int main()
{IOS;int n, q; cin >> n >> q;string s; cin >> s;s = " " + s;int t = log(n) / log(2) + 1;for (int i = 0; i < t; i++)for (int j = 1 << i; j < 1 << (i + 1); j++)mp[j] = i;//注意数组越界assert(1 << t < 3e5);for (int k = 0; k < 3; k++)for (int j = 1; j <= n; j++)if (s[j] == 'W') f[k][j][0] = 1;else if (s[j] == 'L' && k) f[k][j][0] = -1;for (int j = 1; j < t; j++)for (int i = 1; i <= n - (1 << j) + 1; i++){int p = i + (1 << (j - 1));f[0][i][j] = f[0][i][j - 1] + f[(0 + f[0][i][j - 1]) % 3][p][j - 1];f[1][i][j] = f[1][i][j - 1] + f[(1 + f[1][i][j - 1]) % 3][p][j - 1];f[2][i][j] = f[2][i][j - 1] + f[(2 + f[2][i][j - 1]) % 3][p][j - 1];//假设第一维的值为k//注意:不能像上面的预处理一样单独循环三遍不同的k,因为当前状态的k可能会用到不同k值的状态}int l, r, p;while (q--){int ans;cin >> l >> r >> ans;//倍增思想的应用while (l <= r){ans += f[ans % 3][l][mp[r - l + 1]];l += 1 << mp[r - l + 1];}cout << ans << endl;}return 0;
}