难道这道题只能用结构体来创建节点吗?

P4513 小白逛公园

Astk @ 2020-07-31 18:46:36

我偏不信,用数组写了一个线段树,查询的时候定义了一个新的变量存合并后的节点,然后进行查询。 我感觉这个想法没什么问题呀。 然而。。。。。。。它wa了. 下面是我的代码

#include<cstdio>
#include<iostream> 
#define mid (l+r>>1)
#define N 500010
using namespace std;
int sum[N<<2],dat[N<<2],lmax[N<<2],rmax[N<<2],ans,n,m,a[N];
void up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    dat[rt]=max(dat[rt<<1],max(dat[rt<<1|1],rmax[rt<<1]+lmax[rt<<1|1]));
    lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
    rmax[rt]=max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
}
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=a[l];
        return;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    up(rt);
    printf("rt:%d %d %d %d %d\n",rt,dat[rt],lmax[rt],rmax[rt],sum[rt]);
}
void change(int rt,int l,int r,int k,int val){
    if(l==r){
        sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=val;
        return;
    }
    if(k<=mid) change(rt<<1,l,mid,k,val);
    else change(rt<<1|1,mid+1,r,k,val);
    up(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        return rt;
    }
    if(R<=mid) return query(rt<<1,l,mid,L,R);
    if(L>mid)return query(rt<<1|1,mid+1,r,L,R);
    int t1=query(rt<<1,l,mid,L,R),t2=query(rt<<1|1,mid+1,r,L,R);
    printf("t1:%d t2:%d",t1,t2);
    dat[ans]=max(dat[t1],max(dat[t2],rmax[t1]+lmax[t2]));
    lmax[ans]=max(lmax[t1],sum[t1]+lmax[t2]);
    rmax[ans]=max(rmax[t2],sum[t2]+rmax[t1]);
    sum[ans]=sum[t1]+sum[t2];
    printf("rt:%d %d %d %d %d\n",rt,dat[ans],lmax[ans],rmax[ans],sum[ans]); 
    return ans;
}
int main(){
    ans=N<<2-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1){
            if(x>y)swap(x,y);
            printf("%d\n",dat[query(1,1,n,x,y)]);
        }
        else
        change(1,1,n,x,y);
    }
}

用数组不能做是吗?


by Astk @ 2020-07-31 19:35:32

@万弘 那样的话得开nlogn的空间,就得N*20空间才行了吧


by Astk @ 2020-07-31 19:38:52

@天命之路 嗯嗯,应该是有点问题的,可是我想不通,到底是在哪里出现了问题。感觉又好像没什么问题啊


by 万弘 @ 2020-07-31 19:41:46

@Astk 但其实这次询问用过的点可以下次再拿来用,所以没啥大问题


by 万弘 @ 2020-07-31 19:42:27

*这次询问新建过的点


by 天命之路 @ 2020-07-31 19:44:19

@Astk 你的 ans 一直是 N<<2-1,所以你的 t1,t2 也都是N<<2-1(除开函数开头的特判)


by Astk @ 2020-07-31 19:49:59

@天命之路 哦,对


by Astk @ 2020-07-31 19:51:03

@天命之路 我一直觉得t1,t2至多1个为ans,然后以我那个算法就对了,但是它向下递归,左右子树都可能变成ans,这样就错了


by Astk @ 2020-07-31 19:51:54

明白了明白了@万弘 你说的那个方法可行


by Astk @ 2020-07-31 19:52:28

但是我不打数组的代码了,结构体多香啊


by 天命之路 @ 2020-07-31 19:52:57

主要是你的 ans 应该当做一个计数器来用(以新建结点)


上一页 | 下一页