【ST表】【单调队列】Window（jzoj 1326）,nokia手机铃声

文件名：【ST表】【单调队列】Window（jzoj 1326）,nokia手机铃声 【ST表】【单调队列】Window（jzoj 1326） Window jzoj 1326 题目大意

给你一个序列a和一个数k，让你求a中所有长为k的子序列的最大值和最小值

输入样例 8 31 3 -1 -3 5 3 6 7 输出样例 -1 -3 -3 -3 3 33 3 5 5 6 7

数据范围 $20$ $100$

解题思路

方法一： 滚动ST表（不多做解释）

代码1: #include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long using namespace std;int n, k, m, r, f[2][1000010], mf[2][1000010];int main(){memset(mf, 127/3, sizeof(mf));memset(f, -127/3, sizeof(f));scanf("%d %d", &n, &k);for (int i = 1; i <= n; ++i){scanf("%d", &f[0][i]);mf[0][i] = f[0][i];}m = log2(k);for (int j = 1; j <= m; ++j){memset(mf[j&1], 127/3, sizeof(mf[j&1]));//滚动memset(f[j&1], -127/3, sizeof(f[j&1]));for (int i = 1; i <= n - (1<<j) + 1; ++i){f[j&1][i] = max(f[(j + 1)&1][i], f[(j + 1)&1][i + (1<<(j - 1))]);//st表mf[j&1][i] = min(mf[(j + 1)&1][i], mf[(j + 1)&1][i + (1<<(j - 1))]);} }for (int i = 1; i <= n - k + 1; ++i){r = i + k - 1;printf("%d ", min(mf[m&1][i], mf[m&1][r - (1<<m) + 1]));//求解}putchar(10);for (int i = 1; i <= n - k + 1; ++i){r = i + k - 1;printf("%d ", max(f[m&1][i], f[m&1][r - (1<<m) + 1]));}return 0;}

---

方法二： 我们用单调队列来存最大/小值，如果不是更优的就丢掉，如果超过了也丢掉

代码 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long longusing namespace std;int n, m, tail, head, h[1000100], a[1000100];int main(){scanf("%d %d", &n, &m);tail = 0;head = 1;for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);if (head <= tail && h[head] < i - m + 1) head++;//如果过了那就丢掉while(head <= tail && a[h[tail]] > a[i]) tail--;//如果比前面的小，那前面的丢掉h[++tail] = i;//存进去if (i >= m) printf("%d ", a[h[head]]);//这样下来最前面的就是最小的}tail = 0;head = 1;putchar(10);for (int i = 1; i <= n; ++i)//同上{if (head <= tail && h[head] < i - m + 1) head++;while(head <= tail && a[h[tail]] < a[i]) tail--;h[++tail] = i;if (i >= m) printf("%d ", a[h[head]]);}return 0;}