线段树

作者： 作者的头像   橙外 ,  2021-07-18 16:20:12 ,  所有人可见 ,  阅读 399

2


1

The Child and Sequence

思路

$$ 若 x < p, x mod p = x $$

$$ 若 x \geqslant p, xmodp < \frac{x}{2} $$

Hotel G

这题的思想还是用$head[]$数组维护一段区间的前缀最大值,$end[]$数组维护后缀最大值,然后$lazy[]$数组需要分两种情况即可

这题我们还学到查询如何查询区间的端点$=>$就是找到单点的时候返回端点即可

Can you answer these queries I ~好题~

这题本想直接如果节点是负数,就用0替换掉,然后继续push_up
但是想到如果区间都是负数,最终答案会是0这个错误答案

正解:

父节点的最大子段和可以分为三种情况

  1. 区间的前缀最大值
    • 左儿子前缀的最大值
    • 左儿子的值+右儿子前缀的最大值
  2. 区间的中间最大值
    • 左儿子的值
    • 右儿子的值
    • 左儿子的后缀最大值+右儿子的前缀最大值
  3. 区间的后缀最大值
    • 右儿子的后缀最大值
    • 右儿子的值+左儿子的后缀最大值

就算有思路我还是写了快一个早上

一开始我是用纯数组写的
但是写+改两个多小时发现好像不能做到query的时候时时更新不同层次的点的Tree节点的值
然后又改回结构体写
重载运算符就是时时更新此时的答案(push_up也许只是附带作用)

序列操作

用线段树维护区间的8个信息,即$cnt_0, cnt_1, head_0, head_1, end_0, end_1, mid_0, mid_1$

然后要多注意细节:在赋值操作时,这个点已经被打上了取反标记,那取反标记就失效了,因为赋值操作会把取反操作覆盖(光这个我改了很久很久)

区间最大公约数

由区间修改想到维护差分数组 又有$gcd(x, y, z) = gcd(x, y - x, z - y)$

则区间查询$gcd$也可以实现

创作乐曲 杭电多校

从后往前遍历, 维护每一个数$a[i]$, 找到最近的值在$[a[i] - k, a[i]]$的$min_idx[i]$下标, 和最近的值在$[a[i], a[i] + l]$的$max_idx[i]$下标, 每次询问的时候$DP$

因为值域很大, 所以需要动态开点

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

typedef long long LL;

const int N = 100010;

struct Node
{
    int l, r;
    int idx;
}tr[N * 100];

int n, idx;
LL m, k, a[N];
int min_idx[N], max_idx[N];

void pushup(int u)
{
    tr[u].idx = min(tr[tr[u].l].idx, tr[tr[u].r].idx);
}

void update(int &u, LL l, LL r, LL k, int id)
{
    if (!u) u = ++ idx;

    if (l == r)
    {
        tr[u].idx = id;
        return ;
    }

    LL mid = l + r >> 1;
    if (k <= mid) update(tr[u].l, l, mid, k, id);
    else update(tr[u].r, mid + 1, r, k, id);
    pushup(u);
}

int query(int u, LL l, LL r, LL x, LL y)
{
    if (x <= l && r <= y) return tr[u].idx;

    LL mid = l + r >> 1;

    int res = n + 1;
    if (x <= mid) res = min(res, query(tr[u].l, l, mid, x, y));
    if (y > mid) res = min(res, query(tr[u].r, mid + 1, r, x, y));
    return res;
}

void solve()
{
    idx = 0;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i ++) cin >> a[i];
    // tr[0].idx = n + 1是因为pushup的时候可能没有左(右)儿子, 那编号就为0, 所以但是要维护区间最小值, 所以给一个比较大的值
    // tr[1].idx = n + 1是因为一开始只有一个节点, 初始化节点
    tr[0].idx = tr[1].idx = n + 1;

    int root = 0;
    for (int i = n; i >= 1; i --)
    {
        // 注意边界
        min_idx[i] = query(1, 1ll, m, max(1ll, 1ll * a[i] - k), a[i]);
        max_idx[i] = query(1, 1ll, m, a[i], min(m, 1ll * a[i] + k));
        update(root, 1ll, m, a[i], i);
    }

    int q;
    cin >> q;
    vector<int> f(n + 1);
    while (q --)
    {
        int l, r;
        cin >> l >> r;
        // 每次查询的时候都要先清空
        for (int i = l; i <= r; i ++) f[i] = 0;
        int res = 0;
        // 从后往前做比较方便
        for (int i = r; i >= l; i --)
        {
            f[i] = 1;
            if (min_idx[i] <= r)
                f[i] = max(f[i], f[min_idx[i]] + 1);
            if (max_idx[i] <= r)
                f[i] = max(f[i], f[max_idx[i]] + 1);
            res = max(res, f[i]);
        }
        cout << r - l + 1 - res << endl;
    }

    for (int i = 1; i <= idx; i ++)
        tr[i] = {0, 0, 0};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T --) solve();
    return 0;
}

CF2000H

母题: 在一段区间中, 有多个点符合要求, 需要找满足条件的值最小的点->查询的时候二分

0 评论