数据水?

P1440 求m区间内的最小值

coyangjr @ 2018-10-17 11:03:55

自己写的单调队列,结果把while写成if了。AC过了 结果后面的题才发现

#include <bits/stdc++.h>
#define il inline
#define re register
using namespace std;

#define MAXN 2000005

template <typename T>il void scan(T &x)
{
    re int w=0;char ch=0;x=0;
    while (!isdigit(ch))    w|=ch=='-',ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if (w)  x=-x;
}

int q[MAXN];
int a[MAXN];
int tail=0,head=1;
int n,m;

int main()
{
    scan(n);scan(m);
    for (re int i=1;i<=n;i++)   scan(a[i]);
    for (re int i=1;i<=n;i++)
    {
        printf("%d\n",a[q[head]]);
        //if (i-q[head]+1>m&&head<=tail)    head++;
        //就是这里
        while (i-q[head]+1>m&&head<=tail)   head++;
        while (a[i]<a[q[tail]]&&head<=tail) tail--;
        q[++tail]=i;
    }
    return 0;
}

by 花里心爱 @ 2018-10-17 11:07:15

@coyangjr 这个题用if没问题(因为一次最多删一个数)


by coyangjr @ 2018-10-17 11:09:02

@Irressey 好像是的。qwq


by 星小雨 @ 2018-10-17 11:34:21

区间?最小值?
这不是裸st表么= =


by hellomath @ 2018-10-17 11:57:00

区间?最小值? 这不是裸线段树么= =


by 会打沙包的猫 @ 2018-10-23 21:36:35

明明是裸树状数组


|