求助,线段树被卡一个点

P1440 求m区间内的最小值

wwhOvO @ 2020-02-10 10:29:19

用了快读,配合 printf,但最后一个点还是 T 了。。。。求大佬帮忙指正qwq

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int n,m;
long long a[10000100*7];
struct SegmentTree
{
    int l,r;
    long long dat;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].dat
};
SegmentTree t[10000010*4];

inline int read()
{
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r){sum(p)=a[l];return ;}
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=min(sum(p*2),sum(p*2+1));
}

long long ask(int p,int l,int r)
{
    if(l<=l(p)&&r>=r(p))return sum(p);
    int mid=(l(p)+r(p))>>1;
    long long ans=(1<<30);
    if(l<=mid)ans=min(ans,ask(p*2,l,r));
    if(r>mid)ans=min(ans,ask(p*2+1,l,r));
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    for(int i=1;i<=n;i++){if(i==1)printf("0\n");else if(i<=m)printf("%lld\n",ask(1,1,i-1));else printf("%lld\n",ask(1,i-m,i-1));}
    return 0;
}

by Meatherm @ 2020-02-10 10:31:20

没救力,单调队列罢


by Smile_Cindy @ 2020-02-10 10:31:24

@BinaryTree

老老实实单调队列不好吗,为什么会有人尝试用别的结构AC此题?


by wwhOvO @ 2020-02-10 10:36:52

@Alpha @Meatherm 我吸氧过了2333


by chenxinyang2006 @ 2020-02-10 10:42:44

@BinaryTree 草,线段树吸氧可以过2 \times 10 ^ 6也是绝了


by chenxinyang2006 @ 2020-02-10 10:43:14

我写的线段树极限大概就是5 \times 10 ^ 5,这就是写法的问题吗?


by Dzhao @ 2020-02-10 11:18:12

当然会T,要用单调队列呀,线段树是O(nlogn)的,你这题n\leq2×10^6怎么过


by wwhOvO @ 2020-02-10 11:24:07

@Dzhao 然而O2优化就过了(大草)


by 万弘 @ 2020-02-10 11:24:53

草,为什么我的线段树极限10^6,您的线段树2\times 10^6都能过啊,怕了


by Dzhao @ 2020-02-10 11:27:02

那您可能是神仙@BinaryTree


by Dzhao @ 2020-02-10 11:28:13

或者是数据水


| 下一页