蒟蒻求教。。50分，其他的都TLE了。。。

Hydrogen_Matrix @ 2019-10-30 11:27:56

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N = 1000005,oo = 0x7fffffff;
ll n,k;
ll tree1[N<<2],a[N],tree2[N<<2];
inline void read(long long &x){
    char ch,last(' ');
    for (;(ch=getchar())<'0' || ch>'9';last=ch);
    for (x=0;ch>='0' && ch<='9';ch=getchar())
        x = x*10+ch-'0';
    if (last=='-') x = -x;
}
inline void up1(int root){
    tree1[root] = min(tree1[root<<1],tree1[root<<1|1]);
}
inline void up2(int root){
    tree2[root] = max(tree2[root<<1],tree2[root<<1|1]);
}
inline void create(int root,int L,int R){
    if(L==R) {
        tree1[root] = a[L];
        tree2[root] = a[L];
        return ;
    }
    int mid(L+R>>1);
    create(root<<1,L,mid);
    create(root<<1|1,mid+1,R);
    up1(root);
    up2(root);
}
inline int query1(int root,int L,int R,int x,int y){
    if(x>R||y<L) return oo;
    if(x<=L&&R<=y) return tree1[root];
    int mid(L+R>>1);
    int k=oo;
    if(y<=mid) k = min(k,query1(root<<1,L,mid,x,y));
    if(x>mid)   k = min(k,query1(root<<1|1,mid+1,R,x,y));
    else k = min(query1(root<<1,L,mid,x,y),query1(root<<1|1,mid+1,R,x,y));
    return k;
}
inline int query2(int root,int L,int R,int x,int y){
    if(x>R||y<L) return -oo;
    if(x<=L&&R<=y) return tree2[root];
    int mid(L+R>>1);
    int k=-oo;
    if(y<=mid) k = max(k,query2(root<<1,L,mid,x,y));
    if(x>mid)   k = max(k,query2(root<<1|1,mid+1,R,x,y));
    else k = max(query2(root<<1,L,mid,x,y),query2(root<<1|1,mid+1,R,x,y));
    return k;
}
int main(){ 
//  ios::sync_with_stdio(false);
    fill(tree1+1,tree1+4*N+1,oo);
    fill(tree2+1,tree2+4*N+1,-oo);  
    read(n);
    read(k);
//  cin>>n>>k;
    for(int i=1;i<=n;i++) read(a[i]);
    create(1,1,n);
    for(int i=1;i<=n-k+1;i++){
        printf("%d ",query1(1,1,n,i,i+k-1));
//      cout<<query1(1,1,n,i,i+k-1)<<" ";
    }
    printf("\n");
//  cout<<endl;
    for(int i=1;i<=n-k+1;i++){
//      cout<<query2(1,1,n,i,i+k-1)<<" ";
        printf("%d ",query2(1,1,n,i,i+k-1));        
    }   
    return 0;
}

by 1saunoya @ 2019-10-30 11:29:49

您写假了吧。。。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std ;

inline int rd() { int x = 0 ; int f = 1 ; register char c ;
#define gc c = getchar()
    while(isspace(gc)) ;
    if(c == '-') f = -1 , gc ;
    while(x = (x<<1) + (x<<3) + (c&15) , isdigit(gc)) ;
    return x * f ;
#undef gc
}

const int inf = INT_MAX >> 1 ;
const int N = 1e6 + 10 ;

struct node {
    int l , r ;
    int Min , Max ;
#define lt k << 1
#define rt k << 1 | 1
}tree[N << 2] ;

int n , m ;
int a[N] ;

inline void build(int k,int l,int r) {
    if(l > r) return ;
    if(l == r) {
        tree[k].l = l , tree[k].r = r ;
        tree[k].Min = a[l] ;
        tree[k].Max = a[l] ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(lt , l , mid) ;
    build(rt , mid + 1 , r) ;
    tree[k].l = l , tree[k].r = r ;
    tree[k].Min = min(tree[lt].Min , tree[rt].Min) ;
    tree[k].Max = max(tree[lt].Max , tree[rt].Max) ;
}

inline int query(int k,int l,int r,int x,int y) {
    if(l > r) return 0 ;
    if(l >= x and r <= y) return tree[k].Min ;
    int mid = (l + r) >> 1 ;
    int sum = inf ;
    if(x <= mid) sum = min(sum , query(lt , l , mid , x , y)) ;
    if(y > mid) sum = min(sum , query(rt , mid + 1 , r , x , y)) ;
    return sum ;
}
inline int Query(int k,int l,int r,int x,int y) {
    if(l > r) return 0 ;
    if(l >= x and r <= y) return tree[k].Max ;
    int mid = (l + r) >> 1 ;
    int sum = -inf ;
    if(x <= mid) sum = max(sum , Query(lt , l , mid , x , y)) ;
    if(y > mid) sum = max(sum , Query(rt , mid + 1 , r , x , y)) ;
    return sum ;
}

signed main() {
    for(register int i=1;i<=(N<<2);i++) tree[i].Max = -inf , tree[i].Min = inf ;
    n = rd() , m = rd() ;
    for(register int i=1;i<=n;i++) a[i] = rd() ;
    build(1 , 1 , n) ;
    for(register int i=m;i<=n;i++) {
        int x = i - m + 1 , y = i ;
        printf("%d " , query(1 , 1 , n , x , y)) ;
    }
    puts("") ;
    for(register int i=m;i<=n;i++) {
        int x = i - m + 1 , y = i ;
        printf("%d " , Query(1 , 1 , n , x , y)) ;
    }
    return 0 ;
}

by Hydrogen_Matrix @ 2019-10-30 11:37:07

@清风ღ 写假是什么意思？？

by ♨♨♨♨ @ 2019-10-30 11:47:33

滑动窗口不是单调队列吗

by qian_shang @ 2019-10-30 12:10:36

是全世界只有窝一个人用的是单调队列吗

by king12138 @ 2019-10-30 12:48:45

线段树查区间最大最小

by Hydrogen_Matrix @ 2019-10-30 12:48:49

单调队列也可以写，，但是我想用线段树试一下，，但是却运行得很慢，答案是对的，还要优化吗？

by CreeperLordVader @ 2019-10-30 12:53:04

@Hydrogen_ 必须优化,这题必须得 O(N) 过,线段树已经不可能了

by Hydrogen_Matrix @ 2019-10-30 13:23:47

@CreeperLordVader 可是我的朋友用线段树就过了，，可我的就是过不了

by 1195247062hero @ 2019-11-03 08:41:40

@Hydrogen_ 这题不过的原因可能是您写的不优美常数大，理论上来说可以过，您可以试一试BIT， 但限于这道题是单调队列模板题，大佬您想要用线段树强搞，蒟蒻也没有办法orz

by 1195247062hero @ 2019-11-03 08:47:07

大佬您可以试一试吸氧再用一个c++17 您应该就能过了，但小蒟蒻还是建议您学习一下单调队列（大佬可能不屑于写）然后再写一下这道题目