2021牛客暑期多校训练营6 H、Hopping Rabbit

题目大意

小兔子在一个二维的格点图中跳跃，每次它都会沿着正负方向共个方向移动个单位长度。

现在地图中有个陷阱，陷阱是以矩阵的方式存在的，问你有没有一种方法让小兔子在某个起点随意乱跳的情况下都不会掉入任何一个陷阱，你要输出这个起点，或者。

Solution

考点：线段树维护扫描线

首先由于地图本质上是无穷大的，但是对于这样的任意一个矩阵来说，由于小兔子的步长一定为，所以都一定可以离散到这样的初始矩阵中，所以我们按照覆盖关系可以将个陷阱离散到初始矩阵里面，接下来就是要去这个初始矩阵里面找是不是有那个格点它没有被任何一个矩阵覆盖，如果我们固定轴那么轴就变成了一个扫描线问题。

但是显而易见的，如果我们对于每个都暴力的的维护一个扫描线，这样时间复杂度是的会超时。

我们就要想要一个更优秀的方式去维护轴的扫描线，对于区间问题，常用的工具就是线段树了。

我们在树上开出一个懒惰标记，很显然这个懒惰标记一定只有和等于的两种情况，那么当某个区间懒惰标记很显然这个区间的合法长度应该是，那么当懒惰标记退为了怎么办呢？当这个区间是叶子的时候我们就把区间长度赋值成就行，如果不是叶子的话，我们应该保留之前它左右孩子的区间长度之和。因为这个大区间被剔除，小区间可能还是存在一定长度的。例如已经被删除，但是还在扫描线里面，甚至都在扫描线里面。所以我们还是需要等于之前那个区间长度。

接下来就看区间的区间长度是否等于即可判断是不是存在空点了，时间复杂度。特殊的输出答案我们用树上二分的思想，找到那个长度不满足的叶子节点就行了。

const int N = 1e5 + 7;

struct Node {
#define mid (l + r >> 1)
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls,l,mid
#define rson rs,mid+1,r

    ll len[N << 2], cnt[N << 2];
    void push_up(int rt, int l, int r) {
        if (cnt[rt])    len[rt] = r - l + 1;
        else if (l == r)    len[rt] = 0;
        else len[rt] = len[ls] + len[rs];
    }

    void update(int rt, int l, int r, int L, int R, ll v) {
        if (L <= l && r <= R) {
            cnt[rt] += v;
            push_up(rt, l, r);
            return;
        }
        if (L <= mid)    update(lson, L, R, v);
        if (R > mid)    update(rson, L, R, v);
        push_up(rt, l, r);
    }
    ll query(int rt, int l, int r) {
        if (l == r)    return l;
        if (len[ls] < mid - l + 1)    return query(lson);
        else return query(rson);
    }
#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}A;

vector<tup> G[N];
vector<pai> add[N], del[N];
int n, d;

void push(int x1, int x2, vector<pai>& seg) {
    if (x2 - x1 >= d) {
        seg.push_back({ 0,d - 1 });
    }
    else if (x1 % d <= (x2 - 1) % d) {
        seg.push_back({ x1 % d ,(x2 - 1) % d });
    }
    else {
        seg.push_back({ 0, (x2 - 1) % d });
        seg.push_back({ x1 % d, d - 1 });
    }

}



int solve() {
    n = read(), d = read();
    const int P = (1 << 30) / d * d; // 坐标偏移
    for (int i = 1; i <= n; ++i) {
        int X1 = read() + P, Y1 = read() + P, X2 = read() + P, Y2 = read() + P;
        vector<pai> seg1, seg2;
        push(X1, X2, seg1);
        push(Y1, Y2, seg2);
        for (auto& [l, r] : seg1) {
            for (auto& seg : seg2) {
                add[l].push_back(seg);
                del[r + 1].push_back(seg);
            }
        }
    }
    for (int i = 0; i < d; ++i) {
        for (auto& [l, r] : add[i])
            A.update(1, 0, d - 1, l, r, 1);
        for (auto& [l, r] : del[i])
            A.update(1, 0, d - 1, l, r, -1);
        if (A.len[1] < d) {
            puts("YES");
            cout << i << " " << A.query(1, 0, d - 1) << endl;
            return 1;
        }
    }
    puts("NO");

    return 1;
}