蒟蒻线段树RE两个点,求大佬赐教..

P1440 求m区间内的最小值

DEVILK @ 2017-12-10 19:53:08

不知道为什么我的线段树第二个第十个点RE,

数组开得超出了数据范围1000多,还都用的long long

求解为何RE..

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
typedef long long ll;
const ll N=2000000+1055;
const ll INF=INT_MAX;
ll minv[N],vi[N];
ll lson(ll x){return x<<1;}
ll rson(ll x){return x<<1|1;}
ll ql,qr;
ll Query(ll o,ll L,ll R)
{
    ll M=L+((R-L)>>1),ans=INF;
    if(ql<=L&&qr>=R) return minv[o];
    if(ql<=M) ans=min(ans,Query(lson(o),L,M));
    if(qr>M) ans=min(ans,Query(rson(o),M+1,R));
    return ans;
}
ll p,v;
void Update(ll o,ll L,ll R)
{
    ll M=L+((R-L)>>1);
    if(L==R) minv[o]=v;
    else
    {
        if(p<=M) Update(lson(o),L,R);
        else Update(rson(o),M+1,R);
        minv[o]=min(minv[lson(o)],minv[rson(o)]);
    }
}
void BdSegT(ll o,ll L,ll R)
{
    ll M=L+((R-L)>>1);
    if(L==R) minv[o]=vi[L];
    else
    {
        BdSegT(lson(o),L,M);
        BdSegT(rson(o),M+1,R);
        minv[o]=min(minv[lson(o)],minv[rson(o)]);
    }
}
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&vi[i]);
    BdSegT(1,1,n);
    for(int i=1;i<=n;i++)
    {
        if(i==1){
            printf("0\n");
            continue;
        }
        if(i<=m)
        {
            ql=1,qr=i-1;
            ll ans=Query(1,1,n);
            printf("%lld\n",ans);
            continue;
        }
        ql=i-m,qr=i-1;
        ll ans=Query(1,1,n);
        printf("%lld\n",ans);
    }
}

by DEVILK @ 2017-12-10 20:04:30

明白了..不过RE变成了TLE..


by cszmc2004 @ 2017-12-10 20:22:16

这道题要用单调队列,线段树会t


by DEVILK @ 2017-12-26 21:42:32

哦哦哦


by Gypsophila @ 2018-01-15 15:17:16

实测开O2+线段树+快读能A(最慢点476ms)


|