## 题目描述有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。例如，对于序列 $\[1,3,-1,-3,5,3,6,7\]$ 以及 $k = 3$，有如下过程： $$\\def\\arraystretch{1.2} \\begin{array}{|c|c|c|}\\hline \\textsf{窗口位置} & \\textsf{最小值} & \\textsf{最大值} \\\\ \\hline \\verb!\[1 3 -1\] -3 5 3 6 7 ! & -1 & 3 \\\\ \\hline \\verb! 1 \[3 -1 -3\] 5 3 6 7 ! & -3 & 3 \\\\ \\hline \\verb! 1 3 \[-1 -3 5\] 3 6 7 ! & -3 & 5 \\\\ \\hline \\verb! 1 3 -1 \[-3 5 3\] 6 7 ! & -3 & 5 \\\\ \\hline \\verb! 1 3 -1 -3 \[5 3 6\] 7 ! & 3 & 6 \\\\ \\hline \\verb! 1 3 -1 -3 5 \[3 6 7\]! & 3 & 7 \\\\ \\hline \\end{array} $$ ## 输入格式输入一共有两行，第一行有两个正整数 $n,k$。第二行 $n$ 个整数，表示序列 $a$ ## 输出格式输出共两行，第一行为每次窗口滑动的最小值第二行为每次窗口滑动的最大值 ## 样例 #1 ### 样例输入 #1 ```markup 8 3 1 3 -1 -3 5 3 6 7 ``` ### 样例输出 #1 ```markup -1 -3 -3 -3 3 3 3 3 5 5 6 7 ``` ## 提示【数据范围】对于 $50\\%$ 的数据，$1 \\le n \\le 10^5$；对于 $100\\%$ 的数据，$1\\le k \\le n \\le 10^6$，$a\_i \\in \[-2^{31},2^{31})$。 ## 题解 ```cpp #include using namespace std; struct n1 { int num, z; n1(int x, int y) { num = x; z = y; } bool operator<(const n1 x) const { return (z > x.z) || (z == x.z && num < x.num); } }; struct n2 { int num, z; n2(int x, int y) { num = x; z = y; } bool operator<(const n2 x) const { return (z < x.z) || (z == x.z && num < x.num); } }; priority_queue q; priority_queue p; int n, k, top, a[1000010], ans1[1000010], ans2[1000010]; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= k; i++) { q.push(n1(i, a[i])); p.push(n2(i, a[i])); } ans1[++top] = q.top().z, ans2[top] = p.top().z; for (int i = k + 1; i <= n; i++) { q.push(n1(i, a[i])); p.push(n2(i, a[i])); while (i - q.top().num >= k) q.pop(); while (i - p.top().num >= k) p.pop(); ans1[++top] = q.top().z, ans2[top] = p.top().z; } for (int i = 1; i <= top; i++) printf("%d ", ans1[i]); cout << endl; for (int i = 1; i <= top; i++) printf("%d ", ans2[i]); cout << endl; return 0; } ```

线段树

洛谷P1886 滑动窗口 /【模板】单调队列

洛谷P1168 中位数