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
明明是裸树状数组