求助
求助
老师也没看出来
orz
by fantasticJimmy @ 2024-03-28 21:01:19
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e4+5;
const int inf=1e9;
struct node{
int l,r,max,min;
}a[maxn<<2];
int n,q,h[maxn];
void build(int u,int l,int r){
a[u].l=l;//建树
a[u].r=r;//建树
if(l==r){
a[u].max=a[u].min=h[l];
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build((u<<1)+1,mid+1,r);
a[u].max=max(a[u<<1].max,a[(u<<1)+1].max);
a[u].min=min(a[u<<1].min,a[(u<<1)+1].min);
return;
}
int query(int u,int l,int r){
if((a[u].l>=l)&&(a[u].r<=r)){
return a[u].max;
}
int Max=0;
if(a[u<<1].r>=l) Max=max(Max,query(u<<1,l,r));
if(a[(u<<1)+1].l<=r) Max=max(Max,query((u<<1)+1,l,r));
return Max;
}
int query1(int u,int l,int r){
if(a[u].l>=l&&a[u].r<=r){
return a[u].min;
}
int Min=inf;
if(a[u<<1].r>=l) Min=min(Min,query1(u<<1,l,r));
if(a[(u<<1)+1].l<=r) Min=min(Min,query1((u<<1)+1,l,r));
return Min;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>h[i];
}
build(1,1,n);
// cout<<1<<'\n';
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
cout<<query(1,l,r)-query1(1,l,r)<<'\n';
}
return 0;
}
```
不谢,你的代码我没看出来有什么问题,给你看我的
by liukelin @ 2024-03-28 21:03:30
还有其他大佬吗
by fantasticJimmy @ 2024-03-28 21:05:08
@[fantasticJimmy](/user/977425) 我是蒟蒻,不是大佬啊
by liukelin @ 2024-03-28 21:05:40
到底哪有问题
by fantasticJimmy @ 2024-03-28 21:05:59
有点奇怪,好像没什么问题
by Lawrence001 @ 2024-03-28 21:18:05
调出来了,是ls和rs的问题,不要定义成全局变量,要不然查询的时候节点i可能调用了ls,然后rs就被改了,返回之后再调用rs的时候rs的值已经变了,就会不停递归下去。
代码:
```
//test fantasticJimmy
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,h[50005];
struct node{
int l,r,max,min;
}a[4*50005+1];
void build(int x,int l,int r)
{
a[x].l=l;
a[x].r=r;
if(l==r)
{
a[x].max=a[x].min=h[l];
return;
}
int mid=((l+r)>>1);
build(x*2,l,mid);
build(x*2+1,mid+1,r);
a[x].max=max(a[x*2].max,a[x*2+1].max);
a[x].min=min(a[x*2].min,a[x*2+1].min);
return;
}
int query(int i,int l,int r)
{
if(l<=a[i].l&&a[i].r<=r)return a[i].max;
int ma=0,mid=(a[i].l+a[i].r)/2;
if(l<=mid) ma=max(ma,query(i*2,l,r));
if(r>=mid+1) ma=max(ma,query(i*2+1,l,r));
return ma;
}
int query2(int i,int l,int r)
{
if(a[i].l>=l&&a[i].r<=r) return a[i].min;
int mi=1e9,mid=(a[i].l+a[i].r)/2;
if(l<=mid) mi=min(mi,query2(i*2,l,r));
if(r>=mid+1) mi=min(mi,query2(i*2+1,l,r));
return mi;
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>h[i];
build(1,1,n);
for(int i=1;i<=q;i++)
{
int a,b;
cin>>a>>b;
cout<<(query(1,a,b)-query2(1,a,b))<<'\n';
}
return 0;
}
```
by Lawrence001 @ 2024-03-28 21:24:13
我就把这两个全局变量去掉了,直接改成i*2和i*2+1了。
by Lawrence001 @ 2024-03-28 21:25:12
我就把这两个全局变量去掉了,直接改成i×2和i×2+1了。
by Lawrence001 @ 2024-03-28 21:25:52
@[Lawrence001](/user/778881) 谢谢
by fantasticJimmy @ 2024-03-31 09:03:36