震惊，萌新初学信竞，入门难度！？

resftlmuttmotw @ 2018-12-08 11:43:52

#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:46:36

嗯，你的算法是线段树啊，复杂度为线性对数阶O(NlogN)，然而这题无情卡了log，所以去学一下单调队列吧~

by yijan @ 2018-12-08 11:47:29

by Kevin_Wa @ 2018-12-08 11:47:32

@fzszkl 我的线段树过了

by Kevin_Wa @ 2018-12-08 11:48:05

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
struct node{
    int l,r,w,f;
}tree[N*4];
int x,y,z,i,a[N],n,m;
void build(int k,int t,int w)
{ int mid;
    if (t>w) return;
    if (t==w)
      {
        tree[k].l=t;tree[k].r=w;
        tree[k].w=a[t];
        tree[k].f=a[t];
        return;
      }
    mid=(t+w)/2;
    build(k*2,t,mid);
    build(k*2+1,mid+1,w);
    tree[k].l=t;tree[k].r=w;
    tree[k].w=min(tree[k*2].w,tree[k*2+1].w);
    tree[k].f=max(tree[k*2].f,tree[k*2+1].f);
}
int ask1(int k,int t,int w)
{ int mid;
if (t>w) return 0;
    if (x<=t&&w<=y)
      {
        return tree[k].w;
      }
    mid=(t+w)/2;
    int sum=INT_MAX;
    if (x<=mid)sum=min(sum,ask1(k*2,t,mid));
    if (y>mid)sum=min(sum,ask1(k*2+1,mid+1,w));
    return sum;
}
int ask2(int k,int t,int w)
{ int mid;
if (t>w) return 0;
    if (x<=t&&w<=y)
      {
        return tree[k].f;
      }
    mid=(t+w)/2;
    int sum=-INT_MAX;
    if (x<=mid)sum=max(sum,ask2(k*2,t,mid));
    if (y>mid)sum=max(sum,ask2(k*2+1,mid+1,w));
    return sum;
}
int read(int &x)
{
    char c=getchar();int f=1;
    x=0;
    while (c<'0'||c>'9')
      {
      if (c=='-') f=-1;
      c=getchar();
      }
    while (c>='0'&&c<='9')
      {
        x=x*10+(int)c-48;
        c=getchar();
      }
    return x*f;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(n);m=read(m);
    for (int i=1;i<=4*N;i++) 
      {
        tree[i].f=-INT_MAX;
        tree[i].w=INT_MAX;
      }
    for (int i=1;i<=n;i++) a[i]=read(a[i]);
    build(1,1,n);
    for (int i=m;i<=n;i++)
      { int c;
        x=i-m+1;y=i;
        printf("%d ",ask1(1,1,n));
      }
    printf("\n");
    for (int i=m;i<=n;i++)
      { int c;
        x=i-m+1;y=i;
        printf("%d ",ask2(1,1,n));
      }
}

by Kevin_Wa @ 2018-12-08 11:48:31

emm可能是快读的问题

by Juan_feng @ 2018-12-08 11:48:32

@fzszkl 线段树可过qwq

by resftlmuttmotw @ 2018-12-08 11:48:38

@fzszkl

可我逛了一圈题解，有人用线段树搞出来了

by Reaepita @ 2018-12-08 11:49:03

@fzszkl RMQ可以过吧

by yijan @ 2018-12-08 11:50:22

可是它们能不能过和这是个单调队列的板子题又有什么关系呢

by resftlmuttmotw @ 2018-12-08 11:53:12

@yijan

好像很有道理的样子

我还是自己学一下单调队列吧

楼下的不用再回了