resftlmuttmotw @ 2018-12-08 11:43:52
AC 了 很多点
然而 TLE 了 三个点
求救
#include <queue>
#include <cstdio>
#include <climits>
using namespace std;
const int MAXN = 1000001;
int num[MAXN];
class Ans
{
public:
int MIN,MAX;
}pr[MAXN];
Ans Push(int y,int x)
{
Ans a;
a.MIN = x;
a.MAX = y;
return a;
};
template<typename T>
inline T Min(T a,T b) {if(a < b) return a;return b;}
template<typename T>
inline T Max(T a,T b) {if(a > b) return a;return b;}
class M
{
public:
int MAX,MIN;
}ans[MAXN * 4];
inline void tree_built(int l,int r,int k)
{
if(l == r)
{
ans[k].MAX = ans[k].MIN = num[l];
return;
}
int mid = l + r >> 1;
tree_built(l,mid,k << 1);
tree_built(mid + 1,r,k << 1 ^ 1);
ans[k].MIN = Min(ans[k << 1].MIN,ans[k << 1 ^ 1].MIN);
ans[k].MAX = Max(ans[k << 1].MAX,ans[k << 1 ^ 1].MAX);
}
inline Ans query(int l,int r,int k,int Left,int Right)
{
if(r < Left||l > Right) return Push(-1,INT_MAX);
if(l >= Left&&r <= Right)
return Push(ans[k].MAX,ans[k].MIN);
int mid = l + r >> 1;
Ans x1 = query(l,mid,k << 1,Left,Right);
Ans x2 = query(mid + 1,r,k << 1 ^ 1,Left,Right);
return Push(Max(x1.MAX,x2.MAX),Min(x1.MIN,x2.MIN));
}
int main()
{
int i,n,k;
scanf("%d%d",&n,&k);
for(i = 1;i <= n;i++)
scanf("%d",&num[i]);
tree_built(1,n,1);
for(i = 1;i + k - 1 <= n;i++)
{
pr[i] = query(1,n,1,i,i + k -1);
printf("%d ",pr[i].MIN);
}
putchar('\n');
for(i = 1;i + k - 1 <= n;i++)
printf("%d ",pr[i].MAX);
}
by 替罪羊树 @ 2018-12-08 11:53:17
楼上卡log的说法我不同意，因为我用multiset都可以过掉这道题，详见我的题解
by ousuimei_68 @ 2018-12-08 12:11:34
666orz
by henrytb @ 2018-12-08 12:31:37
高端卡常警告
by Substitute0329 @ 2018-12-08 12:39:30
#include<bits/stdc++.h>
using namespace std;
int a[1000001],q[1000001],num[1000001]={0};
int fax[1000001],fin[1000001];
int k,n,head,tail;
inline void dpmin(){
head=1;tail=0;
for(int i=1;i<=n;i++){
while(num[head]<i-k+1&&head<=tail)head++;//维护队头
while(a[i]<=q[tail]&&head<=tail)tail--;//维护队尾
num[++tail]=i;q[tail]=a[i];
fin[i]=q[head];
}
}
inline void dpmax(){
head=1;tail=0;
for(int i=1;i<=n;i++){
while(num[head]<i-k+1&&head<=tail)head++;
while(a[i]>=q[tail]&&head<=tail)tail--;
num[++tail]=i;q[tail]=a[i];
fax[i]=q[head];
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
dpmin();dpmax();
for(int i=k;i<=n;i++)printf("%d ",fin[i]);
printf("\n");
for(int i=k;i<=n;i++)printf("%d ",fax[i]);
printf("\n");
return 0;
}