1
已解决
李庚午
中级守护
中级守护
线段树写的……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了。