2023-01-01

训练记录

$\color{#52C41A} \text{P3740 [HAOI2014]贴海报}$

区间覆盖问题。

法一｜离散化线段树

值域很大 $0 \le N \le 10000000$
数量很少 $1 \le M \le 1000$

考虑离散化。

由于区间夹缝不好处理，将左右端点附近的数加入值域。

void Discrete() {
    for (int i = 1; i <= M; i++) {
        range.push_back(A[i] - 1);
        range.push_back(A[i]);
        range.push_back(A[i] + 1);
        range.push_back(B[i] - 1);
        range.push_back(B[i]);
        range.push_back(B[i] + 1);
    }
    std::sort(range.begin(), range.end());
    range.erase(std::unique(range.begin(), range.end()), range.end());
    for (int i = 1; i <= M; i++) {
        A[i] = std::lower_bound(range.begin(), range.end(), A[i]) - range.begin();
        B[i] = std::lower_bound(range.begin(), range.end(), B[i]) - range.begin();
    }
    return;
}

同时，线段树的值域也要根据离散化值域放缩。

    SGT.Build(SGT.root, 1, M * 5);

从最新贴上的海报开始处理。

用线段树修改查询 $[A_i, B_i]$ 内是否有未覆盖的子区间，若存在打上标记并计数。

    for (int i = M; i >= 1; i--) {
        appeared = false;
        SGT.Modify(SGT.root, A[i], B[i]);
        if (appeared) ans++;
    }

    void Modify(int xNode, int l, int r) {
        if (node[xNode].vis) return;

    }

    void PushUp(int xNode) {
        node[xNode].vis = node[node[xNode].lNode].vis && node[node[xNode].rNode].vis;
        return;
    }

法二｜浮水法

后面写专栏讲。

法三｜暴力

为什么暴力模拟能过？

双倍经验

$\color{#3594D3} \text{UVA1608 Non-boring sequences}$

值域很大 $\text{The elements arenon-negative integers less than} 10^9.$
数量很少 $1 \le n \le 200000$

考虑离散化。

从元素角度考虑。

找到上一个与 $a_i$ 相同的元素下标作为前驱，记为 $last_i$，若未找到则为 $0$；
找到下一个与 $a_i$ 相同的元素下标作为后继，记为 $next_i$，若未找到则为 $n + 1$。

满足下述条件的区间 $[l, r]$一定为 $\text{Non-boring sequences}$：

$l \in (last_i, i]$；
$r \in [i, next_i]$。

因为要求 $a_i$ 在 $[l, r]$ 中出现且仅出现一次。

转化为区间覆盖问题。

以 $l$ 为横轴；
以 $r$ 为纵轴。

转化为扫描线面积并问题。

__stdcall 称之为 $\text{unique}$ 模型。

很恶心。

调了一两个小时。

数据范围

根据讨论区，要开 long long。

否则 $\text{WA}$。

多测清零

各种用到的数据都要清零。

    for (long long i = 1; i <= n; i++) appear[i].clear();

    event.clear();

    SGT.Clear();

清零时可以适当缩减范围。

    void Clear() {
        cnt = 0;
        root = 0;
        for (long long i = 0; i <= (maxN * 4); i++) {
            node[i].l = 0;
            node[i].r = 0;
            node[i].lNode = 0;
            node[i].rNode = 0;
            node[i].tag = 0;
            node[i].sum = 0;
        }
        return;
    }

每一组数据都以 $maxN$ 为界限会 $\text{TLE}$。

    void Clear() {
        cnt = 0;
        root = 0;
        for (long long i = 0; i <= (n * 4); i++) {
            node[i].l = 0;
            node[i].r = 0;
            node[i].lNode = 0;
            node[i].rNode = 0;
            node[i].tag = 0;
            node[i].sum = 0;
        }
        return;
    }

结构体排序

struct Event {
    long long x;
    long long y1, y2;
    long long delta;

    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return delta < other.delta;
    }
};

其实这道题并没用到那么多条件。

struct Event {
    long long x;
    long long y1, y2;
    long long delta;

    bool operator<(const Event& other) const {
        return x < other.x;
    }
};

但是存在一些题需要根据 $delta$ 增减性确定顺序。

具体是啥暂时还想不到例子。

$\text{STL}$ 容器边界

    for (long long i = 1; i <= n; i++) {
        for (long long j = 0; j < appear[i].size(); j++) {
            if (appear[i].size() == 1) {
                last[appear[i][j]] = 0;
                next[appear[i][j]] = n + 1;
                continue;
            }
            if (j == 0) {
                last[appear[i][j]] = 0;
                next[appear[i][j]] = appear[i][j + 1];
                continue;
            }
            if (j == appear[i].size() - 1) {
                last[appear[i][j]] = appear[i][j - 1];
                next[appear[i][j]] = n + 1;
                continue;
            }
            last[appear[i][j]] = appear[i][j - 1];
            next[appear[i][j]] = appear[i][j + 1];
        }
    }

$\text{STL}$ 容器越界访问会 $\text{RE}$。

所以要分情况讨论。

推荐用手写基础数据结构。

但是我不喜欢。