UPC 排队(线段树||RMQ||树状数组||分块处理)

简介: UPC 排队(线段树||RMQ||树状数组||分块处理)

线段树教做人

排队

时间限制: 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好写~


目录
打赏
0
0
0
0
108
分享
相关文章
【算法训练营】队列 合集(1) 933. 最近的请求次数 || LCR 041. 数据流中的移动平均值 || 1700. 无法吃午餐的学生数量
【算法训练营】队列 合集(1) 933. 最近的请求次数 || LCR 041. 数据流中的移动平均值 || 1700. 无法吃午餐的学生数量
96 0
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
CF220B Little Elephant and Array(扫描线+树状数组)
CF220B Little Elephant and Array(扫描线+树状数组)
105 0
UPC Graph (最小生成树 || 并查集+二分)
UPC Graph (最小生成树 || 并查集+二分)
106 0
HDOJ/HDU 1297 Children’s Queue(推导~大数)
HDOJ/HDU 1297 Children’s Queue(推导~大数)
155 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等