Algorithm23 数据结构 区间问题

[TOC]

数据结构 区间问题

单个区间

区间求和:

  • 单次查询: *

  • 多次查询:

    • 【固定长度的滑动窗口】单调队列(适用于固定串口)
    • 【不固定长度,任意起点终点】RMQ [Range maximum/minimun Query]
    • 【不固定长度,任意起点终点】线段树

区间最值:

区间最长递增子序列「LIS问题」:

  • 线性dp

区间逆序对数/区间相互交换次数:

  • 归并排序,记录逆序对数
  • 树状数组

区间其他问题:

  • 求区间中连续抽出相同高度之后的总次数:「思维问题」同时抽取转换为一次遍历

两个区间

  • 最长公共子序列「LCS问题」

区间最值-固定长度区间+滑动询问

https://www.luogu.com.cn/problem/P2032

https://www.luogu.com.cn/problem/P1440

https://www.luogu.com.cn/problem/P2251

https://www.luogu.com.cn/problem/P1886

固定长度区间最大 // 固定长度区间最小 // 固定长度区间最小 // 固定长度区间最大和最小

「单调队列思路」思路:维护一个优先队列(也就是堆结构),然后往里边push,往外拿,输出顶的

  • 往里边push:无脑每次往里边push
  • 往外拿:每次先遍历,遍历到索引不在合适的区间内的,然后给pop掉【理解成从堆里把不符合的内容揪出来】
  • 输出顶的:直接每次把堆顶拿出来

数据结构:通过pair来将值和索引进行绑定,【借助优先队列】默认对值进行排序,根据(less选取最大)(greater选取最小)对堆进行更新。

#include <iostream>
using namespace std;
const int maxn = 1e6+9;
int n, k, a[maxn], ans_max[maxn], ans_min[maxn], idx;
typedef pair<int, int> pr;
#include <queue>
priority_queue<pr, vector<pr>, less<pr>> pq_max;
priority_queue<pr, vector<pr>, greater<pr>> pq_min;


int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    for (int i = 1; i <= n; ++i) {
        pq_max.push(make_pair(a[i], i));
        pq_min.push(make_pair(a[i], i));
        if (i >= k) {
            while (i-k >= pq_max.top().second) pq_max.pop();
            ans_max[++idx] = pq_max.top().first;
            while (i-k >= pq_min.top().second) pq_min.pop();
            ans_min[idx] = pq_min.top().first;
        }
    }
    for (int i = 1; i <= idx; ++i) printf("%d ", ans_min[i]);
    printf("\n");
    for (int i = 1; i <= idx; ++i) printf("%d ", ans_max[i]);
    return 0;
}

「RMQ的ST表思路」

首先初始化,得到一个数组,然后再利用得到的数组进行查询。

数据结构:如果是求min,则用minn[i][k],表示起点为i,倍数为k的点,这个点在数组中的最小值的区域范围。(同理max的话用maxx[i][k]

算法:首先要预处理,预处理的方式就是通过遍历倍数,然后再对所有起点进行遍历,将这个minn数组和maxx数组来完善起来

区间逆序对问题

树状数组:声明一个c数组用来存放的是树状数组的内容,

树状数组:用lowbit进行倍数上的跳转 => 单点修改+区域求和 // 区域修改+输出单点 // 四种操作融合在一起

#define lowbit(x) x&(-x)
const int maxn = 1e5+9;
int c[maxn];

// 单点修改=>从上往下都要加,因为上面代表的和也包括下边的和=>下边代表的pos是大的,所以最后跳出的条件是pos<=n
void single_add(int pos, int k) {while (pos <= n) {c[pos] += k; pos += lowbit(pos);}}

// 区间查询,这个query可以得到这个点之前的所有的和「前缀和」,所以区域就可以看作是两个前缀和相减
int query(int pos) {int ans = 0;whlie (pos >= 1) {ans += c[pos];pos -= lowbit(pos);}}
Posted on Feb 1, 2021