python/TangDou/AcWing/SegmentTree/HDU5820.md

##[$Lights$ 灯](http://acm.hdu.edu.cn/showproblem.php?pid=5820)

### 一、题目大意
给出一个$n*m$的矩阵，再给出$N$个点,问其中的任意两个点 $(x_1,y_1)$ 与 $(x_2,y_2)$ 之间，最短路径为 $|x_1-x_2| + |y_1-y_2|$ , 是否存在一条最短路径，**使得拐弯的地方都存在着点**。

[视频讲解](https://www.bilibili.com/video/BV1Tk4y1m7VM)

**目前状态：理解了，但不太会讲，还需要继续消化一下~ 2023.01.05**

#### 值得学习的内容

* **二维坐标去重+按(x,y)排序的办法**

* 思维：思考两个点，必须得$x$相等或$y$相等，否则无法连接上，需要引入第三点。此时，如果两个点是按($x,y$)排序过的，那么可以在同$x$，同$y$情况下讨论相邻点的情况。思考构建一个矩形，矩形内有其它点就是$NO$,这个思维难度也不低。

* 为什么要用主席树+扫描线？因为方便，无脑，按顺序 $x$从小到大，每个 $x$视为一个版本，每次查询构造矩形中点的个数，如果大于$0$就是有不合法的点

也不怪我学着费劲，本题对思维的要求确实挺高，没学习过类似的题，现场基本是不可能做上的，都需要提前做过类似的训练，并且熟练才行，慢慢历练吧~


### 二、扫描线+主席树

对于每个点$(x, y)$，**正左方** 最近的点记为$(x', y)$ 
<font color='red' size=3><b>解读：
① 正左方意味着$y$坐标相同
② 最近也意味着$y$坐标相同
</b></font>

**正上(下)** 方最近的点记为$(x, y')$，
<font color='red' size=3><b>解读：
① 正上（下）方意味着$x$坐标相同
② 最近也意味着$x$坐标相同
</b></font>

* 如果以这$3$个点为顶点的矩形内部存在有其它的点$(x'', y'')$，则从$(x, y)$到$(x'', y'')$不存在$good$ $path$. 
* 反之，如果整个图中都不存在这种情况，则任意两点间都有$good$ $path$

因而可以用 **扫描线和可持久化线段树** 来做，从左往右扫描，每个$x$值 **对应线段树的一个版本**，每遇到一个点$(x, y)$和它正上（下）方最近的点$(x, y')$就在当前版本的线段树和版本为$x'$的线段树上查询$y$和$y'$之间的点数，如果这两个值不相等，则意味着存在上述的点$(x'',y'')$. 对于每条扫描线处理完查询之后再将点插入到当前版本的线段树中. 复杂度$O(NlogN)$。

对于每个$x$，在其每个$y$处对线段树进行更新，并记录左边最近的点的横坐标，最后再将该$x$与最后版本的线段树对应起来。从左向右扫一遍，先判断，后更新。

#### 实现代码
```cpp {.line-numbers}
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int N = 500010;
const int M = 50010;

int n;            //点的数量
vector<int> a[M]; //记录每个点的坐标

//主席树的结构体
struct Node {
    int cnt;
    int l, r;
} tr[N << 5]; //主席树，一般开32倍空间
int idx;      //主席树的节点生成器
int root[M];  //版本与根节点的对应关系
int ver[M];   //记录y坐标是在哪个版本加入进去的,这是一个桶，性能用静态数组模拟应该是最强的，不要使用什么unordered_map之流

//标准的主席树insert
int insert(int p, int l, int r, int x) {
    int q = ++idx;
    tr[q] = tr[p];
    tr[q].cnt++;
    if (l == r) return q;
    int mid = (l + r) >> 1;
    if (x <= mid)
        tr[q].l = insert(tr[p].l, l, mid, x);
    else
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
    return q;
}

//功能：主席树，在两个版本间 查询 某个区间中数字的增加个数
int query(int q, int p, int ql, int qr, int l, int r) {
    if (ql <= l && qr >= r) return tr[p].cnt - tr[q].cnt; //完整区间包含,直接返回两个版本的数字个数差，表示两个版本间增加的数字数量
    int ans = 0;
    int mid = (l + r) >> 1;
    if (ql <= mid) ans = query(tr[q].l, tr[p].l, ql, qr, l, mid);     //递归查询左半区间
    if (qr > mid) ans += query(tr[q].r, tr[p].r, ql, qr, mid + 1, r); //递归查询右半区间
    return ans;
}

bool solve() {
    //对于主席树的0号版本进行清空
    root[0] = idx = tr[0].l = tr[0].r = tr[0].cnt = 0; //索引号生成器idx修改为0，主席树中0号结点左儿子，右儿子都不存在，0号版本中数字个数为0, 0号版本的根节点是0
    memset(ver, 0, sizeof(ver));                       //清空ver数组

    for (int i = 1; i <= 50000; i++) {                          //从小到大枚举每一个x坐标
        for (int j = 0; j < a[i].size(); j++) {                 //从小到大枚举每一个y坐标
            //如果是第一个y坐标，那么l=0,这个0是哨兵的意思。如果不是第一个y坐标，那么l=当前y坐标的前一个y坐标，prev_y,
            int l = j == 0 ? 0 : a[i][j - 1];

            //如果是最后一个y坐标，那么r=50001,否则r=当前y坐标的下一个y坐标，next_y
            int r = j == a[i].size() - 1 ? 50001 : a[i][j + 1];

            // root[i]:当前版本的根
            // root[x[a[i][j]]]:前一版本的根
            // query的返回值是个整数，表示两个版本间两个区间内增加的数字个数，如果个数大于0，就return false
            if (query(root[i - 1], root[ver[a[i][j]]], l + 1, r - 1, 1, 50000)) return false;
        }

        root[i] = root[i - 1];
        for (int j = 0; j < a[i].size(); j++) {           //从小到大枚举每一个y坐标
            root[i] = insert(root[i], 1, 50000, a[i][j]);
            ver[a[i][j]] = i; //记录a[i][j]这个y坐标，是第i个版本中增加进去的
        }
    }
    //如果上面所有的坐标点都讨论过，全都没有返回false,那就只能返回true
    return true;
}

/*
  NO
  YES
*/
int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("HDU5820.in", "r", stdin);
#endif

    while (n = read(), n) { //在使用快读时，要注意使用 ,n 而不是使用 && n!!!! read没有返回值！！！！

        // a数组装的是坐标(x,y),只不过它是以x坐标为第一维，第二维的y1,y2,y3,... 通过push_back加入到一维的x中
        for (int i = 0; i < M; i++) a[i].clear(); //二维vector的清空操作，不用循环还真不行

        int x, y;
        while (n--) {
            x = read(), y = read(); // 每个点的坐标
            a[x].push_back(y);      // 记录每个点的坐标，记录的方法很有意思，是一个vector,一维是x坐标，二维是y坐标
        }

        //枚举每个可能的x坐标，对x坐标相同的点，按y坐标小由到大进行排序，这样，就是一个二维有序的数组啦，和结构体两个属性进行排序效果和速度是一样的
        for (int i = 1; i <= 50000; i++) {                            //这样是以x从小到大排序的
            sort(a[i].begin(), a[i].end());                           //对y也要从小到大排序,这和整一个Node{x,y},然后自定义sort operator < 定义先按x，后按y是一个意思，有时间再写一个结构体版本的
            a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end()); //对于相同的(x,y)进行排序+去重
        }

        //开始每一轮计算的主函数solve
        puts(solve() ? "YES" : "NO"); //存在题目要求的答案，返回YES，否则返回NO
    }

    return 0;
}
```

### 三、$zkw$线段树+扫描线

https://yukizzz.github.io/2016/08/23/HDU-5820-Lights%E3%80%90zkw%E7%BA%BF%E6%AE%B5%E6%A0%91%EF%BC%8C%E6%89%AB%E6%8F%8F%E7%BA%BF%E3%80%91/

https://www.cnblogs.com/Judge/p/9514862.html

https://blog.csdn.net/keshuqi/article/details/52205884