线段树教做人
排队
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
每天,农夫John的N(1 <= N <= 50,000)头牛总是按同一序列排队.有一天,John决定让一些牛们玩一场飞盘比赛.他准备找一群在对列中位置连续的牛来进行比赛.但是为了避免水平悬殊,牛的身高不应该相差太大.
John准备了Q (1 <= Q <= 180,000)个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.
注意: 在最大数据上, 输入和输出将占用大部分运行时间.
输入
第1行: N 和 Q.
第2…N+1行: 第i+1行是第i头牛的身高.
第N+2…N+Q+1行: 每行两个整数A和B(1 <= A <= B <= N), 表示从A到B的所有牛.
输出
第1…Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.
样例输入 Copy
6 3
1
7
3
4
2
5
1 5
4 6
2 2
样例输出 Copy
6
3
0
提示
10%的数据 N,Q<=10
30%的数据 N,Q<=2000
思路一:
让我们求某个区间的最大值和最小值的差值,很容易想到线段树啦,而且没有修改操作,就比较轻松~
线段树真的好容易RE
代码如下
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int n,q,x,y; int b[maxn]; struct node{ int l,r,maxx,minn; }a[maxn*4]; void build(int u,int l,int r){ a[u].l=l;a[u].r=r; if(l==r){ a[u].maxx=b[l]; a[u].minn=b[l]; } else{ int mid=(l+r)/2; build(u<<1,l,mid); build(u<<1|1,mid+1,r); a[u].maxx=max(a[u<<1].maxx,a[u<<1|1].maxx); a[u].minn=min(a[u<<1].minn,a[u<<1|1].minn); } } int qmax(int u,int l,int r){ if(a[u].l==l&&a[u].r==r) return a[u].maxx; int mid=(a[u].l+a[u].r)/2; if(r<=mid) return qmax(u<<1,l,r); else if(l>mid) return qmax(u<<1|1,l,r); else{ int res=max(qmax(u<<1,l,mid),qmax(u<<1|1,mid+1,r)); return res; } } int qmin(int u,int l,int r){ if(a[u].l==l&&a[u].r==r) return a[u].minn; int mid=(a[u].l+a[u].r)/2; if(r<=mid) return qmin(u<<1,l,r); else if(l>mid) return qmin(u<<1|1,l,r); else{ int res=min(qmin(u<<1,l,mid),qmin(u<<1|1,mid+1,r)); return res; } } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&b[i]); build(1,1,n); while(q--){ scanf("%d%d",&x,&y); printf("%d\n",qmax(1,x,y)-qmin(1,x,y)); //cout<<<<endl; } return 0; }
思路二:
关于区间最大最小怎么能够没有RMQ呢!简单好写易上手~
关于RMQ的证明可以看大佬博客 传送门
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=200010,maxm=18; ll n,m; ll a[maxn],dpmax[maxn][maxm],dpmin[maxn][maxm]; void init(){ for(int j=0;j<maxm;j++) for(int i=1;i+(1<<j)-1<=n;i++) if(j==0) dpmax[i][j]=a[i],dpmin[i][j]=a[i]; else{ dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<j-1)][j-1]); dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<j-1)][j-1]); } } ll query(ll l,ll r){ ll len=r-l+1; ll k=log(len)/log(2); return max(dpmax[l][k],dpmax[r-(1<<k)+1][k])-min(dpmin[l][k],dpmin[r-(1<<k)+1][k]); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; init(); while(m--){ int x,y; cin>>x>>y; cout<<query(x,y)<<endl; } return 0; }
思路三:
有线段树了怎么能够没有树状数组呢!好像也挺好写~
直接放大佬博客了~传送门
思路四:
分块处理 传送门
还是RMQ好写~