线段树一片红求助

P1886 滑动窗口 /【模板】单调队列

SalomeJLQ @ 2020-09-07 22:13:26

还是一道水题,用线段树写的,九点WA一点T,

调试的眼都花了,不知道样例怎么就输出了-3 -3 -3 -3 3 33 3 5 5 7 7

改了很多次,越改越错,然后又改回来了,我线段树真的太屑了

所以怎么改,有人给我改一改吗,

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],k;
struct node{int maxn,minn;}t[4000020];
void build(int l,int r,int p){
    if(l==r){t[p].maxn=a[l];t[p].minn=a[l];return;}
    int mid=l+r>>1;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
    t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
//  cout<<l<<" "<<r<<" "<<mid<<" "<<p<<" "<<t[p].maxn<<" "<<t[p].minn<<endl;
}
int askmaxn(int x,int y,int l,int r,int p){
    int max1=-11111,max2=-11111;
    if(l==r)return a[l];
    if(l>y||r<x)return -11111;
    if(l>=x&&r<=y)return t[p].maxn;
    int mid=l+r>>1;
    if(r>=x)max1=askmaxn(x,y,l,mid,p*2);
    if(l<=y)max2=askmaxn(x,y,mid+1,r,p*2+1);
    cout<<x<<" "<<y<<" "<<max1<<" "<<max2<<endl;
    return max(max1,max2);
}
int askminn(int x,int y,int l,int r,int p){
    int min1=99999999,min2=99999999;
    if(l==r)return a[l];
    if(l>y||r<x)return 99999999;
    if(l>=x&&r<=y)return t[p].minn;
    int mid=l+r>>1;
    if(r>=x)min1=askminn(x,y,l,mid,p*2);
    if(l<=y)min2=askminn(x,y,mid+1,r,p*2+1);
    cout<<x<<" "<<y<<" "<<min1<<" "<<min2<<endl;
    return min(min1,min2);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    for(int i=1;i<=n-k+1;i++)cout<<askminn(i,i+k-1,1,n,1)<<" ";
    cout<<endl;
    for(int i=1;i<=n-k+1;i++)cout<<askmaxn(i,i+k-1,1,n,1)<<" ";
    return 0;
}

by Little09 @ 2020-09-07 22:16:42

这不是单调队列吗


by SalomeJLQ @ 2020-09-07 22:22:58

@AC_WA自动机 想用线段树做,

每天花费半小时写一棵线段树,全是bug,,


by 7KByte @ 2020-09-07 22:44:41

极值设小了吧


by ducati @ 2020-11-03 15:42:31

这题宁愿用RMQ做,我也不愿上一棵线段树QAQ


|