Coco_T @ 2016-12-27 19:09:41
一直70分,把最大值和最小值改成long long 就会MLE。。。QAQ 不知道哪里有问题
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
int le,ri,mi,ma;
};
node t[6000100]; //数组开4倍
int a[1000001];
int n,k;
int build(int x,int l,int r)
{
t[x].le=l;
t[x].ri=r;
if (l==r)
{
t[x].ma=a[l];
t[x].mi=a[l];
return 0;
}
build(x*2,l,(l+r)/2);
build(x*2+1,(l+r)/2+1,r);
t[x].mi=min(t[x*2].mi,t[x*2+1].mi);
t[x].ma=max(t[x*2].ma,t[x*2+1].ma);
}
int askmin(int x,int l,int r)
{
if (t[x].le>=l&&t[x].ri<=r)
return t[x].mi;
if (t[x].le>r||t[x].ri<l)
return 1073741824;
return min(askmin(x*2,l,r),askmin(x*2+1,l,r));
}
int askmax(int x,int l,int r)
{
if (t[x].le>=l&&t[x].ri<=r)
return t[x].ma;
if (t[x].le>r||t[x].ri<l)
return 0;
return max(askmax(x*2,l,r),askmax(x*2+1,l,r));
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for (int i=1;i<=n-k+1;i++)
printf("%d ",askmin(1,i,i+k-1));
printf("\n");
for (int i=1;i<=n-k+1;i++)
printf("%d ",askmax(1,i,i+k-1));
return 0;
}
by joyemang33 @ 2016-12-27 19:56:32
此题单调即可,线段树小题大做