暑假集训系列题解（六）

题目1

题目链接

Hopping Rabbit

题目

image-20210802201159515

题解

扫描线+线段树，将陷阱区域映射到(0,0)-(d-1,d-1)的矩形当中，只要查找矩形中为被陷阱覆盖的部分即可。

代码

#include <stdio.h>
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll n, d;
ll num[200500] = {0};
ll lazy[800500] = {0};
ll min1[800500] = {0};
void push_up(ll t)
{
    min1[t] = min(min1[2 * t], min1[2 * t + 1]);
}
void push_down(ll t)
{
    if (lazy[t] == 0)
        return;
    lazy[2 * t] += lazy[t];
    lazy[2 * t + 1] += lazy[t];
    min1[2 * t] += lazy[t];
    min1[2 * t + 1] += lazy[t];
    lazy[t] = 0;
}
void update(ll t, ll l, ll r, ll L, ll R, ll add) ///l,r为更新区间，L,R为线段树区间
{
    if (l <= L && r >= R)
    {
        min1[t] += add;
        lazy[t] += add;
        return;
    }
    push_down(t);
    ll mid = (L + R) / 2;
    if (l <= mid)
        update(2 * t, l, r, L, mid, add);
    if (mid < r)
        update(2 * t + 1, l, r, mid + 1, R, add);
    push_up(t);
}
ll query_pos(ll t, ll l, ll r)
{
    if (l == r)
        return l;
    ll mid = (l + r) / 2;
    push_down(t);
    if (min1[2 * t] == 0)
        return query_pos(2 * t, l, mid);
    else
        return query_pos(2 * t + 1, mid + 1, r);
}
struct node
{
    ll l, r;
};
vector<node> v1[100500], v2[100500];
void clc(ll &x)
{
    x = (x % d + d) % d;
}
void option1(ll x1, ll y1, ll x2, ll y2)
{
    if (x1 >= x2 || y1 >= y2)
        return;
    v1[x1].push_back({y1 + 1, y2});
    v2[x2].push_back({y1 + 1, y2});
}
void option(ll x1, ll y1, ll x2, ll y2)
{
    if (y2 - y1 >= d)
    {
        option1(x1, 0, x2, d);
        return;
    }
    clc(y1), clc(y2);
    if (y1 > y2)
    {
        option1(x1, 0, x2, y2);
        option1(x1, y1, x2, d);
        return;
    }
    else
    {
        option1(x1, y1, x2, y2);
        return;
    }
}
int main()
{
    scanf("%lld%lld", &n, &d);
    for (ll i = 1; i <= n; i++)
    {
        ll x1, y1, x2, y2;
        scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        if (x2 - x1 >= d)
        {
            option(0, y1, d, y2);
            continue;
        }
        clc(x1), clc(x2);
        if (x1 > x2)
        {
            option(0, y1, x2, y2);
            option(x1, y1, d, y2);
        }
        else
        {
            option(x1, y1, x2, y2);
        }
    }
    for (ll i = 0; i < d; i++)
    {
        for (node x : v1[i])
            update(1, x.l, x.r, 1, d, 1);
        for (node x : v2[i])
            update(1, x.l, x.r, 1, d, -1);
        if (min1[1] != 0)
            continue;
        printf("YES\n%lld %lld\n", i, query_pos(1, 1, d) - 1);
        return 0;
    }
    printf("NO\n");
}