灵异线段树求调
查看原帖
灵异线段树求调
767096
TKXZ133楼主2022/12/24 19:01

头一次遇到这么灵异的事。

一份代码加了一个输出,以前的输出就不一样了。

一份代码和另一份代码只有输出的东西不一样,一份能正常运行另一份SF。

调了一个小时,重构了一遍,重写了一遍,死活找不出问题。

求助!

#include <bits/stdc++.h>
using namespace std;
const int N=500500;

int inpa[N],inpb[N];
int n,m,in1,in2,in3;

struct STn{int l,r,maxa,minb,ztoy,ytoz,ans;};

struct ST{
    STn a[N<<2];
    STn merge(STn a,STn b){
        STn res;
        res.maxa=max(a.maxa,b.maxa);
        res.minb=min(a.minb,b.minb);
        res.ztoy=max(max(a.ztoy,b.ztoy),a.maxa-b.minb);
        res.ytoz=max(max(a.ytoz,b.ytoz),b.maxa-a.minb);
        res.ans=max(max(a.ans,b.ans),max(a.ztoy+b.maxa,b.ytoz+a.maxa));
        return res;
    }
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;
        if(a[p].l==a[p].r){
            a[p].maxa=inpa[l];
            a[p].minb=inpb[l];
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        a[p]=merge(a[p<<1],a[p<<1|1]);
        return ;
    }
    void change(int p,int x,int k,int f){
        if(a[p].l==a[p].r){
            if(f==1) a[p].maxa=k;
            if(f==2) a[p].minb=k;
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        if(x<=mid) change(p<<1,x,k,f);
        if(x>mid) change(p<<1|1,x,k,f);
        a[p]=merge(a[p<<1],a[p<<1|1]);
        return ;
    }
    STn ask(int p,int l,int r){
        if(l<=a[p].l&&a[p].r<=r) return a[p];
        int mid=(a[p].l+a[p].r)>>1;
        if(r<=mid) return ask(p<<1,l,r);
        if(l>mid) return ask(p<<1|1,l,r);
        return merge(ask(p<<1,l,r),ask(p<<1|1,l,r));
    }
}tree;

int main(){
    freopen("the.in","r",stdin);
    freopen("the.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&inpa[i]);
    for(int i=1;i<=n;i++) scanf("%d",&inpb[i]);
    tree.build(1,1,n);
    while(m--){
        scanf("%d%d%d",&in1,&in2,&in3);
        if(in1==1) tree.change(1,in2,in3,1);
        if(in1==2) tree.change(1,in2,in3,2);
        if(in1==3) cout<<tree.ask(1,in2,in3).ans<<'\n';
    }
    return 0;
}

也许是我哪里犯了一个愚蠢的错误吧,希望各位大佬帮忙看看。

2022/12/24 19:01
加载中...