首页 > 其他分享 >NC25045 [USACO 2007 Jan S]Balanced Lineup

NC25045 [USACO 2007 Jan S]Balanced Lineup

时间:2023-04-25 21:14:32浏览次数:52  
标签:src return int mi USACO Jan vector 2007 mx

题目链接

题目

题目描述

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 100,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 30) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

输入描述

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

输出描述

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

示例1

输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出

6
3
0

题解

方法一

知识点:线段树。

区间最值板子题,熟悉一下模板。

时间复杂度 \(O((n+q)\log n)\)

空间复杂度 \(O(n)\)

方法二

知识点:ST表。

不需要修改,因此同样也可以ST表做。

时间复杂度 \(O(n\log n + q)\)

空间复杂度 \(O(n)\)

代码

方法一

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct T {
    int mx, mi;
    static T e() { return { (int)-2e9,(int)2e9 }; }
    friend T operator+(const T &a, const T &b) { return { max(a.mx, b.mx),min(a.mi,b.mi) }; }
};

template<class T>
class SegmentTree {
    int n;
    vector<T> node;

    T query(int rt, int l, int r, int x, int y) {
        if (r < x || y < l) return T::e();
        if (x <= l && r <= y) return node[rt];
        int mid = l + r >> 1;
        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
    }

public:
    SegmentTree() {}
    SegmentTree(const vector<T> &src) { init(src); }

    void init(const vector<T> &src) {
        assert(src.size());
        n = src.size() - 1;
        node.assign(n << 2, T::e());
        function<void(int, int, int)> build = [&](int rt, int l, int r) {
            if (l == r) return node[rt] = src[l], void();
            int mid = l + r >> 1;
            build(rt << 1, l, mid);
            build(rt << 1 | 1, mid + 1, r);
            node[rt] = node[rt << 1] + node[rt << 1 | 1];
        };
        build(1, 1, n);
    }

    T query(int x, int y) { return query(1, 1, n, x, y); }
};

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<T> a(n + 1);
    for (int i = 1, x;i <= n;i++) cin >> x, a[i] = { x,x };
    SegmentTree<T> sgt(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto [mx, mi] = sgt.query(l, r);
        cout << mx - mi << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct T {
    int mx, mi;
    static T e() { return { (int)-2e9,(int)2e9 }; }
    friend T operator+(const T &a, const T &b) { return { max(a.mx, b.mx),min(a.mi,b.mi) }; }
};

template<class T>
class ST {
    vector<vector<T>> node;

public:
    ST() {}
    ST(const vector<T> &src) { init(src); }

    void init(const vector<T> &src) {
        assert(src.size());
        int n = src.size() - 1;
        int sz = log2(n);
        node.assign(sz + 1, vector<T>(n + 1));
        for (int i = 1;i <= n;i++) node[0][i] = src[i];
        for (int i = 1;i <= sz;i++)
            for (int j = 1;j + (1 << i) - 1 <= n;j++)
                node[i][j] = node[i - 1][j] + node[i - 1][j + (1 << i - 1)];
    }

    T query(int l, int r) {
        int k = log2(r - l + 1);
        return node[k][l] + node[k][r - (1 << k) + 1];
    }
};

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<T> a(n + 1);
    for (int i = 1, x;i <= n;i++) cin >> x, a[i] = { x,x };
    ST<T> st(a);
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto [mx, mi] = st.query(l, r);
        cout << mx - mi << '\n';
    }
    return 0;
}

标签:src,return,int,mi,USACO,Jan,vector,2007,mx
From: https://www.cnblogs.com/BlankYang/p/17353872.html

相关文章

  • Django之路由层 (有名和无名分组 反向解析 路由分发 名称空间)
    目录一、路由匹配django2.X及以上path第一个参数写什么就匹配什么django1.X第一个参数是正则表达式PS:无论什么版本django都自带加斜杠后缀的功能也可以取消,这里如果在浏览器地址栏没有写完整的/index/,而是/index,这里还是可以找到的,因为Django会帮你二次查找,浏览器会有303......
  • Django框架——路由分发、名称空间、虚拟环境、视图层三板斧、JsonResponse对象、requ
    路由分发#Django支持每个应用都可以有自己独立的路由层、静态文件、模版层。基于该特性多人开发项目就可以完全解耦合,之后利用路由分发还可以整合到一起多个应用都有很多路由与视图函数的对应关系这个时候可以拆分到各自的路由层中使用路由分发之前总路由直接是路由与视图......
  • django打包成whl包并分发
    django打包成whl包并分发python中下载setuptools工具,打包成whl包结构公司内部写的包,只给公司内部使用,可以开源出来公司写好的项目,打包好,发送给客户,客户可以直接运行起来,不需要下载依赖注意:之前下载的第三包都是:requests-2.28.2-py3-none-any.whlwhl结尾的打包好的包,可以......
  • 仿Django框架-基于wsgiref模块和jinja2模块写一个简单的框架 主流框架简介 动静态网
    目录仿Django框架-基于wsgiref模块和jinja2模块写一个简单的框架一、前期需要的了解背景知识web框架的本质理解1:连接前端与数据库的中间介质理解2:socket服务端手写web框架的大概思路1.编写socket服务端代码2.浏览器访问响应无效>>>:HTTP协议3.根据网址后缀的不同获......
  • Django(五)
    Django(五)request对象#GETPOSTFILESmethodpathpath_infoget_full_path()bodydefindex(request):print(request.path)#/index/print(request.path_info)#/index/print(request.get_full_path_info())#接收路径的全部内容连参数也能拿到pr......
  • Django 如何使用 Celery 完成异步任务或定时任务
    以前版本的Celery需要一个单独的库(django-celery)才能与Django一起工作,但从Celery3.1开始,情况便不再如此,我们可以直接通过Celery库来完成在Django中的任务。安装Redis服务端以Docker安装为例,安装一个密码为mypassword的Redis服务端dockerrun-itd--name......
  • Python Django 制作商品列表展示
    新建名为goods应用pythonmanage.pystartappgoods修改chapter1/settings.py文件在INSTALLED_APPS数组中添加goods在对象TEMPLATES.OPTIONS中添加django.template.context_processors.media添加三个常量MEDIA_URL='/media/'MEDIA_ROOT=os.path.join(BASE......
  • Hungry Cow(USACO23 FEB Bronze T1)
    题目: 来写周练了,这道题目开开胃,就只用遍历一遍b数组、d数组再加上一些特判即可程序:#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;longlongn,t,d[N],b[N];intmain(){ios::sync_with_stdio(false);cin>>n>>t;for(inti=1;i<=n;i++)......
  • Django 静态文件 request对象方法 pycharm和Django连接MySQL Django模型层初步了解 基
    目录静态文件一、概念静态文件:不经常变化的文件,主要针对html文件所使用到的各种资源。例如:css文件、js文件、img文件、第三方框架文件ps:Django针对静态文件资源需要单独在根目录创建一个static目录统一存放,该目录下的文件类型还有很多,例如:utils目录,plugins目录,li......
  • django中的主表和从表
    一、主表和从表在Django中,ORM的关系模型中,有主表和从表之分。其中,主表又称为“一方表”,从表也称为“多方表”。这里举个简单的例子:假设有两个模型 Blog 和 Entry,每个 Blog 包含多个 Entry:classBlog(models.Model):name=models.CharField(max_length=100)......