问题标题: 洛谷:P1531 I Hate It(线段树写的)

1
0
已解决
李庚午
李庚午
中级守护
中级守护

线段树写的……Query函数写的莫名爆炸。明明应该是对的啊,蒟蒻求指教。

#include<bits/stdc++.h>
#define MAXN 200000
using namespace std;
int a[MAXN+1];
int tree[MAXN*4];
int n,m;
void push_up(int x)
{
    tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
void build(int l,int r,int p)
{
    if (l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    push_up(p);
    //cout<<"data : "<<tree[p]<<"; id: "<<p<<"; from "<<l<<" to "<<r<<endl;
}
void update(int L,int C,int l,int r,int p)
{
    if(l==r)
    {
        tree[p]=C;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(L,C,l,mid,p<<1);
    else update(L,C,mid+1,r,p<<1|1);
    push_up(p);
}
int query(int nl,int nr,int l,int r,int p)
{
    if ((nl==l)&&(r==nr))
    {
        return tree[p];
    }
    int ans=0;
    int mid=(l+r)>>1;
    if (nr<=mid) return(nl,nr,l,mid,p<<1);
    else if (nl>mid) return(nl,nr,mid+1,r,p<<1|1);
    else return max(query(nl,nr,l,mid,p<<1),query(nl,nr,mid+1,r,p<<1|1));
}//就是这个函数写的应该错了……
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        char ch,x,y;
        cin>>ch>>x>>y;
        if (ch=='Q') cout<<query(x,y,1,n,1)<<endl;
        else update(x,y,1,n,1);
    }
    return 0;
}

我知道那个update写的还有一点细节处理上的问题,但是请先帮我找出Query函数里的错误……拜托各位dalao了。


0
已采纳
葛新
葛新
资深守护
资深守护

提交记录截个图看看

0
0
王星河
王星河
资深光能
资深光能

m的值很小,直接模拟就行了,但是要用 scanf() 和 printf() 。

我AC了。

我要回答