线段树优化dp，abc389F - Rated Range

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

F - Rated Range

二、解题报告

1、思路分析

考虑定义 f(i, j) 为 初始分数为j，经过i 场比赛后的最终分数

f(i, j) = f(i - 1, j) + 1，如果 l[i] <= f(i - 1, j) <= r[i]

否则，f(i, j) = f(i - 1, j)

显然具有单调性 f(i, j + 1) >= f(i, j)

那么说明 f(i) 单调不降

那么我们用懒标记线段树维护 f(i)，每次读入 l(i) r(i)，对f 值 在 l(i) 和 r(i) 之间的线段进行 + 1即可

2、复杂度

时间复杂度： O(nlogn + q)空间复杂度：O(nlogn)

3、代码详解

 ​

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;

    LazySegmentTree() : n(0) {}
    LazySegmentTree(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LazySegmentTree(std::vector<T> _init) {
        init(_init);
    }

    void init(int _n, const Info &_v = Info()) {
        init(std::vector<Info>(_n, _v));
    }

    template<class T>
    void init(const std::vector<T> &_init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());

        auto build = [&](auto &&self, int p, int l, int r) -> void {
            if (l == r) {
                info[p] = _init[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, p * 2, l, m);
            self(self, p * 2 + 1, m + 1, r);
            pull(p);
        };

        build(build, 1, 0, n - 1);
    }

    void pull(int p) {
        info[p] = info[p * 2] + info[p * 2 + 1];
    }

    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }

    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag{};
    }

    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }

        int m = (l + r) / 2;

        push(p);
        if (x < m)
            modify(p * 2, l, m, x, v);
        else
            modify(p * 2 + 1, m + 1, r, x, v);
        pull(p);
    }

    void modify(int x, const Info &v) {
        modify(1, 0, n - 1, x, v);
    }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x)
            return Info{};

        if (x <= l && r <= y) 
            return info[p];

        int m = (l + r) / 2;
        push(p);
        auto t = rangeQuery(p * 2, l, m, x, y) + rangeQuery(p * 2 + 1, m + 1, r, x, y);
        return t;
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n - 1, l, r);
    }

    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) return;

        if (x <= l && r <= y) {
            apply(p, v);
            return;
        }

        int m = (l + r) / 2;

        push(p);
        rangeApply(p * 2, l, m, x, y, v);
        rangeApply(p * 2 + 1, m + 1, r, x, y, v);
        pull(p);
    }

    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 0, n - 1, l, r, v);
    }

    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }

        if (l == r)
            return l;

        int m = (l + r) / 2;
        push(p);
        int res = findFirst(p * 2, l, m, x, y, pred);
        if (res == -1)
            res = findFirst(p * 2 + 1, m + 1, r, x, y, pred);
        return res;
    }

    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n - 1, l, r, pred);
    }

    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred) {
        if (l > y || r < x || !pred(info[p])) {
            return -1;
        }

        if (l == r)
            return l;

        int m = (l + r) / 2;
        push(p);
        int res = findLast(p * 2 + 1, m + 1, r, x, y, pred);
        if (res == -1)
            res = findLast(p * 2, l, m, x, y, pred);
        return res;
    }

    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n - 1, l, r, pred);
    }
};

struct Tag{
    int x = 0;
    void apply(const Tag &t) {
        if (t.x) {
            x += t.x;
        }
    }
};

struct Info{
    int max = 0;

    void apply(const Tag &t) {
        max += t.x;
    }
    friend Info operator+ (const Info &a, const Info &b) {
        return {std::max(a.max, b.max)};
    }
};

struct F0{
    int t = 0;
    bool operator()(const Info& v) {
        return v.max >= t;
    }
};

struct F1{
    int t = 0;
    bool operator()(const Info& v) {
        return v.max > t;
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    constexpr int N = 5E5;
    std::vector<Info> init(N + 1);
    for (int i = 0; i <= N; ++ i) {
        init[i].max = i;
    }
    
    LazySegmentTree<Info, Tag> sgt(init);

    for (int i = 0; i < n; ++ i) {
        int l, r;
        std::cin >> l >> r;

        int L = sgt.findFirst(1, N, F0{l});
        int R = sgt.findFirst(1, N, F1{r});
        if (R == -1) {
            R = N + 1;
        }

        sgt.rangeApply(L, R - 1, {1});
    }

    int q;
    std::cin >> q;

    while (q --) {
        int x;
        std::cin >> x;

        std::cout << sgt.rangeQuery(x, x).max << '\n';
    }

    return 0;
}