dayi @ 2018-09-21 12:33:52
TLE我再优化qwq,为什么WA*8? https://www.luogu.org/recordnew/show/10767127
#include<iostream>
//#include<algorithm>
using namespace std;
#define max(x,y) (x>y)?x:y
#define min(x,y) (x<y)?x:y
#define maxn 1000005
#define INIT_CIN \
ios::sync_with_stdio(false); \
cin.tie(0);
int A[maxn],cnt=1,ans=0;
const int inf = 0x3f3f3f3f;
struct node{
int lc,rc,sum,min,max;
int add;
}a[maxn<<1];
inline void pushup(int u){
a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
a[u].max=max(a[a[u].lc].max,a[a[u].rc].min);
}
inline void build(int u,int l,int r){
if(l==r){
a[u].min=A[l],a[u].max=A[l];
return ;
}
int mid=(l+r)>>1;
a[u].lc=++cnt;
build(a[u].lc,l,mid);
a[u].rc=++cnt;
build(a[u].rc,mid+1,r);
pushup(u);
}
inline void query_max(int u,int l,int r,int ll,int rr){
if(l==ll&&r==rr){
ans=max(a[u].max,ans);
return;
}
int mid=(l+r)>>1;
if(rr<=mid)query_max(a[u].lc,l,mid,ll,rr);
else if(ll>mid)query_max(a[u].rc,mid+1,r,ll,rr);
else{
query_max(a[u].lc,l,mid,ll,mid),query_max(a[u].rc,mid+1,r,mid+1,rr);
}
}
inline void query_min(int u,int l,int r,int ll,int rr){
if(l==ll&&r==rr){
ans=min(a[u].min,ans);
return;
}
int mid=(l+r)>>1;
//pushdown
if(rr<=mid)query_min(a[u].lc,l,mid,ll,rr);
else if(ll>mid)query_min(a[u].rc,mid+1,r,ll,rr);
else{
query_min(a[u].lc,l,mid,ll,mid),query_min(a[u].rc,mid+1,r,mid+1,rr);
}
}
int n,k;
int main()
{
INIT_CIN;
cin>>n>>k;for(int i=1;i<=n;++i){cin>>A[i];}
build(1,1,n);
int t=n-k+1;
for(int i=1;i<=t;++i){//min
register int l=i,r=i+k-1;
// cout<<"de:"<<l<<" "<<r;
ans=inf;
query_min(1,1,n,l,r);
cout<<ans<<" ";
}cout<<endl;
for(int i=1;i<=t;++i){//max
register int l=i,r=i+k-1;
// cout<<"de:"<<l<<" "<<r<<endl;
ans=-inf;query_max(1,1,n,l,r);cout<<ans<<" ";
}
return 0;
}
by royzhu @ 2018-09-21 13:54:33
你能AC两个点已经是奇迹
by royzhu @ 2018-09-21 13:57:07
else
{
ans=min(query_min(a[u].lc,l,mid,ll,mid),ans),min(query_min(a[u].rc,mid+1,r,mid+1,rr),ans);
}
by royzhu @ 2018-09-21 13:57:54
发错了
by royzhu @ 2018-09-21 13:58:06
else
{
ans=min(query_min(a[u].lc,l,mid,ll,mid),ans)
,ans=min(query_min(a[u].rc,mid+1,r,mid+1,rr),ans);
}
by dayi @ 2018-09-21 18:51:15
@royzhu 谢谢dalao回复我、
不过我还是没看懂为什么这样做..
这样直接递归到所在区间,然后更新最值不行嘛..为什么还要递归左孩子和右孩子捏..
by royzhu @ 2018-09-22 13:14:42
我搞错了, 问题不在这。
by royzhu @ 2018-09-22 13:16:08
你这里打错了
inline void pushup(int u){
a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
a[u].max=max(a[a[u].lc].max,a[a[u].rc].min);
}
应该是
inline void pushup(int u){
a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
a[u].max=max(a[a[u].lc].max,a[a[u].rc].max);
}
by dayi @ 2018-09-24 13:28:56
@royzhu 太感谢了!!!