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)