poj2823 Sliding Window（单调队列）

题意：

给定一个长度为 $N$ 的数字序列，要求你求出每个长度为 $K$ 的区间内的最小值与最大值。

单调队列做法：

const int N = 1e6 + 10; const int mod = 998244353; int a[N], maxx[N], minn[N], queue1[N], queue2[N];//queue存位置 int i, n, k, front1, front2, tail1, tail2, cnt; int main() { sdd(n, k); cnt = front1 = front2 = tail1 = tail2 = 1;//front头指针,tail尾指针 rep(i, 1, n) { sd(a[i]); if (i - queue1[front1] >= k) front1++; if (i - queue2[front2] >= k) front2++; if (a[i] >= a[queue1[tail1]]) while (a[i] >= a[queue1[tail1]] && tail1 >= front1) tail1--; queue1[++tail1] = i; if (a[i] <= queue2[tail2]) while (a[i] <= a[queue2[tail2]] && tail2 >= front2) tail2--; queue2[++tail2] = i; if (i >= k) { maxx[cnt] = a[queue1[front1]]; minn[cnt++] = a[queue2[front2]]; } } for (int i = 1; i + k - 1 <= n; i++) printf("%d%c", minn[i], i + k - 1 == n ? '\n' : ' '); for (int i = 1; i + k - 1 <= n; i++) printf("%d%c", maxx[i], i + k - 1 == n ? '\n' : ' '); return 0; }

线段树做法：

const int N = 1e6 + 50; int a[N]; int ans1[N], ans2[N]; struct node { int left, right, mid; int maxn, minn; } w[4 * N]; int build(int l, int r, int root) { if (l == r) { w[root].left = w[root].right = l; w[root].maxn = a[l]; w[root].minn = a[l]; return w[root].maxn; } w[root].left = l; w[root].right = r; w[root].mid = (l + r) / 2; build(l, w[root].mid, 2 * root); build(w[root].mid + 1, r, 2 * root + 1); w[root].maxn = max(w[2 * root].maxn, w[2 * root + 1].maxn); w[root].minn = min(w[2 * root].minn, w[2 * root + 1].minn); return w[root].maxn; } int querymax(int l, int r, int root) { if (w[root].left == l && w[root].right == r) { return w[root].maxn; } else if (l > w[root].mid) { return querymax(l, r, 2 * root + 1); } else if (r <= w[root].mid) { return querymax(l, r, 2 * root); } else { return max(querymax(l, w[root].mid, 2 * root), querymax(w[root].mid + 1, r, 2 * root + 1)); } } int querymin(int l, int r, int root) { if (w[root].left == l && w[root].right == r) { return w[root].minn; } else if (l > w[root].mid) { return querymin(l, r, 2 * root + 1); } else if (r <= w[root].mid) { return querymin(l, r, 2 * root); } else { return min(querymin(l, w[root].mid, 2 * root), querymin(w[root].mid + 1, r, 2 * root + 1)); } } int main() { int n, k; sdd(n, k); rep(i, 1, n) sd(a[i]); build(1, n, 1); for (int i = 1; i + k - 1 <= n; i++) { ans1[i] = querymin(i, i + k - 1, 1); ans2[i] = querymax(i, i + k - 1, 1); } for (int i = 1; i + k - 1 <= n; i++) printf("%d%c", ans1[i], i + k - 1 == n ? '\n' : ' '); for (int i = 1; i + k - 1 <= n; i++) printf("%d%c", ans2[i], i + k - 1 == n ? '\n' : ' '); return 0; }