The question:

Given a sequence of numbers of length N, N, N, you are asked to find the minimum and maximum of each interval of length K, K, K.

Monotonic queue practices:

const int N = 1e6 + 10;
const int mod = 998244353;

int a[N], maxx[N], minn[N], queue1[N], queue2[N];/ / the queue memory location
int i, n, k, front1, front2, tail1, tail2, cnt;

int main(a)
{
    sdd(n, k);
    cnt = front1 = front2 = tail1 = tail2 = 1;//front pointer,tail pointer
    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;
}
Copy the code

Line segment tree approach:

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(a)
{
    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;
}
Copy the code