Aczy156

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