首页 > 其他分享 >洛谷题单指南-常见优化技巧-P2880 [USACO07JAN] Balanced Lineup G

洛谷题单指南-常见优化技巧-P2880 [USACO07JAN] Balanced Lineup G

时间:2024-09-10 15:26:27浏览次数:9  
标签:int 洛谷题 len st 区间 P2880 Balanced 长度 最值

原题链接:https://www.luogu.com.cn/problem/P2880

题意解读:在若干个不定长区间里,求区间最大值与最小值之差

解题思路:

对于区间求最值,通常有几种方式:

1、暴力法,通过枚举所有的区间来计算区间最值

2、单调队列,针对区间长度固定的情况

3、ST表,针对区间长度不固定且元素不会发生改变的情况

4、树状数组,针对区间长度不固定且元素会发生改变的情况

这里显然是一个ST表的模版题。

首先,看看暴力法计算区间最值的过程,以最大值为例:

for(int i = 1; i <= n; i++)
{   
    int maxx = a[i];
    for(int j = i + 1; j <= n; j++)
    {
        maxx = max(maxx, a[j]); //s[i][j]表示从a[i]~a[j]的最大值
        s[i][j] = maxx;
    }
}
        

 要枚举以所有元素开始的所有可能长度区间,整个复杂度是O(n^2)的。

 ST表基于这样的原理:

要计算区间[i, j]的最值,只需要计算[i, k]以及[k, j]的最值,其中[i,k]和[k,j]允许部分重叠

我们不需要预计算所有区间的最值,利用倍增的思想,我们只需要计算从每一个元素i开始,长度为2^j的区间的最值

设st[i][j]表示从i开始,长度是2^j的区间的最大值

根据定义可知:st[i][0] = a[i]

然后对st进行预处理:

for(int j = 1; j <= log2(n); j++) //枚举所有可能的区间长度2^j
{
    for(int i = 1; i + (1 << j) - 1 <= n; i++) //枚举区间起点
    {
        //从i开始长度为2^j的区间最大值 = max(从i开始长度为2^j/2的区间最大值,从i+2^j/2开始长度为2^j/2的区间最大值)
        st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

对于给定区间[l,r],如何计算最大值呢?

首选确定一个区间长度2^len,使得l开始长度为2^len的区间与r结束长度为2^len的区间重叠,这样[l,r]的最大值就是max(st[l][len], st[r-(1<<len)+1][r])

len的计算方式:

int len = log2(r - l + 1);

100分代码:

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

const int N = 50005, M = 20; //M = log2(N) + 5

int n, q;
int a[N];
int st_max[N][M], st_min[N][M];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++)
    {
        st_max[i][0] = st_min[i][0] = a[i];
    }

    for(int j = 1; j <= log2(n); j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
            st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
        }
    }

    int l, r;
    while(q--)
    {
        cin >> l >> r;
        int len = log2(r - l + 1);
        int maxx = max(st_max[l][len], st_max[r - (1 << len) + 1][len]);
        int minx = min(st_min[l][len], st_min[r - (1 << len) + 1][len]);
        cout << maxx - minx << endl;
    }

    return 0;
}

 

标签:int,洛谷题,len,st,区间,P2880,Balanced,长度,最值
From: https://www.cnblogs.com/jcwy/p/18404792

相关文章

  • 洛谷题单指南-常见优化技巧-P1886 滑动窗口 /【模板】单调队列
    原题链接:https://www.luogu.com.cn/problem/P1886题意解读:单调队列模版题。解题思路:采用双端队列维护单调的序列,单调队列三部曲:1、去头,当窗口内元素个数超过k,队头出队2、去尾,当要加入的元素会破坏单调性,队尾出队3、入队,将元素的下标存入队列每一次入队后,队头元素即为窗口最......
  • 洛谷题单指南-常见优化技巧-P3467 [POI2008] PLA-Postering
    原题链接:https://www.luogu.com.cn/problem/P3467题意解读:用长方形的海报覆盖建筑的侧面,最少需要的海报数如上图,左边最少需要3张,右边最少需要4张解题思路:可以看出,需要海报数与建筑宽度无关,只与高度有关。当建筑高度与之前不同时,肯定需要增加一张海报;当建筑高度与之前有相同......
  • 洛谷题单指南-常见优化技巧-P3143 [USACO16OPEN] Diamond Collector S
    原题链接:https://www.luogu.com.cn/problem/P3143题意解读:找到两个不相交的最长连续序列,使得序列最大值和最小值差不超过k,求两个最长的序列长度和。解题思路:先将所有数从小到大排序,记为a[]要找到两个不相交的最长连续序列,可以采用下面技巧:设b[i]表示i之前“差值在k之内的连续......
  • 洛谷题单指南-常见优化技巧-P4653 [CEOI2017] Sure Bet
    原题链接:https://www.luogu.com.cn/problem/P4653题意解读:选中的灯泡中,某一类较少的总权值减去灯泡数量所得到的收益最大值。解题思路:注意,此题关键是:要使得较少的收益最大化1、要最大化,意味着每次应该选择尽可能大权值的灯泡2、要使A、B类中较少的收益最大化,意味着每次应该优......
  • 洛谷题单指南-常见优化技巧-唯一的雪花 Unique Snowflakes
    原题链接:https://www.luogu.com.cn/problem/UVA11572题意解读:本质上是要计算最长连续不重复子序列的长度,典型的双指针应用。解题思路:通过双指针来枚举子序列,右指针指向的元素每次记录元素出现的次数,可以借助hash数组h[]如果枚举到的元素出现次数超过1,则表示左、右指针之间的子......
  • 洛谷题单指南-常见优化技巧-P2216 [HAOI2007] 理想的正方形
    原题链接:https://www.luogu.com.cn/problem/P2216题意解读:在矩阵中找n*n正方形里最大值和最小值差值的最小值。解题思路:1、枚举法直接枚举所有n*n的正方形的位置,然后在遍历求最大值、最小值,复杂度为O(n^4),显然不能通过。2、二维单调队列既然是求正方形范围内的最值,看起来是......
  • 洛谷题单指南-常见优化技巧-P2032 扫描
    原题链接:https://www.luogu.com.cn/problem/P2032题意解读:求滑动窗口内的最大值,典型的单调队列应用。解题思路:单调队列的三部曲:1、去头。已存入的元素个数超过k,则去头。注意队列里存的是元素下标,只需要用当前下标减去队头元素来判断即可。2、去尾。根据单调队列的单调性,如果......
  • 洛谷题单指南-常见优化技巧-P1950 长方形
    原题链接:https://www.luogu.com.cn/problem/P1950题意解读:在一张n*m个格子的纸上,从没有画过的格子中剪出长方形的方案数。解题思路:1、暴力做法枚举所有的子矩阵O(n^4),然后用二维前缀和计算子矩阵的和,通过和来判断子矩阵是否全部是'.'。2、优化做法针对每一行进行处理,计算包......
  • Balanced String
    这道题目真的不知道怎么总结了,这技巧太新了见这篇题解为什么最开始要引入这个子问题呢?实际上,我们假设我们已经得到了最终的交换后的答案,设为\(t\),\(s\)就是题目给的原串,从\(s\)到\(t\)的最小交换次数当然就是从\(t\)到\(s\)的最小交换次数,于是考虑从\(t\)到\(s\)的最小交换次数,......
  • 洛谷题单指南-常见优化技巧-P2866 [USACO06NOV] Bad Hair Day S
    原题链接:https://www.luogu.com.cn/problem/P2866题意解读:每个牛能看到的右边比他矮的牛,直到有比他高的挡住为止,因此只用找每个牛右边第一个比他高的牛的位置即可计算中间比他矮的有多少。解题思路:典型的单调栈应用,注意,常规的单调栈可以用来:1、找每个数左边第一个比他小的数的......