首页 > 其他分享 >NC14402 求最大值

NC14402 求最大值

时间:2023-05-03 15:23:17浏览次数:65  
标签:rt src return int 最大值 node 序列 NC14402

题目链接

题目

题目描述

给出一个序列,你的任务是求每次操作之后序列中 (a[j]-a[i])/(j-i)【1<=i<j<=n】的最大值。

操作次数有Q次,每次操作需要将位子p处的数字变成y.

输入描述

本题包含多组输入,每组输入第一行一个数字n,表示序列的长度。
然后接下来一行输入n个数,表示原先序列的样子。
再接下来一行一个数字Q,表示需要进行的操作的次数。
最后Q行每行两个元素p,y,表示本操作需要将位子p处的数字变成y.
数据范围:
3<=n<=200000
1<=Q<=200000
-1000000000<=a[i]<=1000000000

输出描述

每组数据输出Q行,每行输出一个浮点数,保留两位小数,表示所求的最大值。

示例1

输入

5
2 4 6 8 10
2
2 5
4 9

输出

3.00
3.00

说明

第一次操作之后的序列变成:2 5 6 8 10
第二次操作之后的序列变成:2 5 6 9 10

备注

输入只有整形

题解

知识点:线段树,贪心。

一个巧妙的贪心,原式可以理解为两点的斜率,现在将点顺序画在坐标系上,注意到选择相邻两点的斜率一定比不相邻两点更优,因此我们直接考虑相邻两点的斜率即可。

相邻两点斜率就等于 \(a[j] - a[i]\) ,我们用线段树维护差分数组即可。

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

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

代码

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

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

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

    void update(int rt, int l, int r, int x, F f) {
        if (r < x || x < l) return;
        if (l == r) return node[rt] = f(node[rt]), void();
        int mid = l + r >> 1;
        update(rt << 1, l, mid, x, f);
        update(rt << 1 | 1, mid + 1, r, x, f);
        node[rt] = node[rt << 1] + node[rt << 1 | 1];
    }

    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(int _n = 0) { init(_n); }
    SegmentTree(const vector<T> &src) { init(src); }

    void init(int _n) {
        n = _n;
        node.assign(n << 2, T::e());
    }
    void init(const vector<T> &src) {
        assert(src.size() >= 2);
        init(src.size() - 1);
        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);
    }

    void update(int x, F f) { update(1, 1, n, x, f); }

    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;
    while (cin >> n) {
        vector<int> a(n + 1);
        for (int i = 1;i <= n;i++) cin >> a[i];

        vector<T> a_src(n);
        for (int i = 1;i <= n - 1;i++) a_src[i] = { a[i + 1] - a[i] };
        SegmentTree<T, F> sgt(a_src);

        int m;
        cin >> m;
        while (m--) {
            int p, y;
            cin >> p >> y;
            a[p] = y;
            if (p >= 2) sgt.update(p - 1, { y - a[p - 1] });
            if (p <= n - 1) sgt.update(p, { a[p + 1] - y });
            cout << sgt.query(1, n - 1).mx << ".00" << '\n';
        }
    }
    return 0;
}

标签:rt,src,return,int,最大值,node,序列,NC14402
From: https://www.cnblogs.com/BlankYang/p/17369096.html

相关文章

  • 查询出数据库中char型字段的最大值,查出数据库中字段最大值,max,缺少列,xh...
    SELECTmax(cast(xhasint))asxhFROMkk.kkcltj用cast(xhasint)把varchar(2)的类型转成int后再查出最大值注意:xh的字段里只能存储char型或number型数据,否则会报无效符号错误有时候不主意会写成SELECTmax(cast(xhasint))FROMkk.kkcltj这样select出来的值就没有......
  • 不使用内置函数的情况下,如何使用Python实现求平均值、最大值和最小值?
    今日鸡汤寂寂竟何待,朝朝空自归。大家好,我是Python进阶者。一、前言昨天在Python最强王者交流群【鱼鱼鱼也不】问了一个Pandas处理的问题,下图是讨论截图:下图是他的原始数据:其实一开始是有点难以理解的。其实这个就是想判断两列的情况,用一列值填充另一列值。二、实现过程这里【猫药......
  • 【剑指 Offer】 59 - II. 队列的最大值
    【题目】请定义一个队列并实现函数max_value得到队列里的最大值,要求函数max_value、push_back和pop_front的均摊时间复杂度都是O(1)。若队列为空,pop_front和max_value需要返回-1示例1:输入:["MaxQueue","push_back","push_back","max_value","pop_front","max_va......
  • 【剑指 Offer】 59 - I. 滑动窗口的最大值
    【题目】给定一个数组nums和滑动窗口的大小k,请找出所有滑动窗口里的最大值。示例:输入:nums=[1,3,-1,-3,5,3,6,7],和k=3输出:[3,3,5,5,6,7]解释: 滑动窗口的位置               最大值---------------              -----[1 3 ......
  • java8 lambda 求list最大值、最小值、平均值、求和、中位数、属性排序(空指针异常,空值
    点击查看代码importorg.junit.Test;importjava.text.SimpleDateFormat;importjava.util.*;importjava.util.stream.Collectors;importstaticjava.util.Comparator.comparingLong;importstaticjava.util.stream.Collectors.*;/***@Author:*@Date:2018/12......
  • mysql求多列最大值
    1、使用列转行,每一列都转为一行数据,这样,直接比值就可以了。优点:比较常用,可以不用先求出每行或每列的最大值,转换后直接比值即可。缺点:大量使用union,union越多,性能越差,在数据量大的情况下不推荐。selectymd,max(value)from( selectname,oneasvaluefromt unionall s......
  • 滑动窗口最大值
    给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。1.暴力遍历(超时)暴力法classSolution{public:vector<int>maxSlidingWindow(v......
  • 剑指Offer——59-I.滑动窗口的最大值(c语言)
    title:剑指Offer59-I.滑动窗口的最大值(c语言)给定一个数组nums和滑动窗口的大小k,请找出所有滑动窗口里的最大值。示例:输入:nums=[1,3,-1,-3,5,3,6,7],和k=3输出:[3,3,5,5,6,7]解释:滑动窗口的位置最大值-----------------......
  • 239. 滑动窗口最大值
    设计单调栈classSolution{classMyQueue{Deque<Integer>deque=newLinkedList<>();//弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出publicvoidpoll(intval){if(!deque.isEmpty()&&val==deque.pee......
  • Python入门基础实例讲解——两个数字比大小,并输出最大值
    嗨害大家好鸭!我是小熊猫~今天也是给大家带来干货的一天~pycharm永久激活码可以从这里找到我:输出:print()print()方法用于打印输出,最常见的一个函数。比较运算符>:大于,如果运算符前面的值大于后面的值,则返回True;否则返回False<:小于,如果运算符前面的值小于后面的值,则返回True;否......