2022牛客多校 C Grab the Seat!

题意

二维平面，屏幕是 (0, 1)–(0, m) 的线段
有 n 行 m 列座位在屏幕前面，是坐标范围 1 ≤ x ≤ n, 1 ≤ y ≤ m 的整点
有 k 个座位已经有人，求出到屏幕的视线不被任何人挡住的座位数量
q 次询问，每次修改一个人的坐标后求出答

题解
对于 y = 1 或 y = m 的列，每个人只会挡住自己正右方的人。特殊处理
一下。
而对于 y = 2, 3, . . . , m − 1，每个人挡住的区域是 (0, 1) 和 (0, m) 到这个
点的两条射线之间的区域。两条射线的方向都是 x 坐标增大，y 坐标一个增
大一个减小。最后不合法的区域就是这些区域的并集。
整个区域实际上构成一个折线图。对于每个 y，会有一个分界线 t，在这
一列上，x ∈ [1, t) 的点是满足条件的，而 x ∈ [t, n] 的点会被挡住。
折线图由 2k 个线段构成。这 2k 条线段有比较明显的性质，就是延长线
都经过 (0, 1) 或 (0, m)。可以把它们分成两类。
那么实际上可以对于延长线经过这两个点的线段分别维护一下斜率。
首先对每个 y，如果这一列有多个人，那么肯定考虑 x 最小的人，因为
小的会完全覆盖大的。
然后对于 (0, 1) 和 (0, m) 分开考虑。
以 (0, 1) 为例，所有线段都是从某个点往右上方走。
如果按 y 从小到大加入线段，不难发现斜率大的线段一旦加入，就一直
会覆盖斜率小的线段。对于某个 y，要找到最小的合法 x，那么肯定取的是
前面所有线段中斜率最大的线段。所以对 y 正着扫一遍，在扫的同时维护一
下最大的斜率，即可得出每一列只考虑经过 (0, 1) 的线段的答案。
(0, m) 同理，倒着扫一遍维护斜率最小（绝对值最大）的线段即可。每
个 y 在两种情况取 min 就是答案。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  //保留小数setprecision
#define endl 'n'
#define PI acos(-1.0) // 3.1415
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define lowbit(x) x & -x
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define int long long
//#pragma GCC optimize(2)
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 7, M = 5e5 + 7;
const int mod = 1e9 + 7;

int n, m, k, q;
int h[N], X[N], Y[N], MIN[N];

struct node
{
    int a, b;
    bool operator<(const node &x) const //按照斜率从大到小排序,斜率是b/a,不等式转移就是下面的式子,这个式子从小到大对应斜率从大到小。
    {
        return a * x.b < x.a * b;
    }
};

inline void work()
{

    fill(h + 1, h + m + 1, n);
    fill(MIN + 1, MIN + m + 1, n + 1);

    for (int i = 1; i <= k; i++) //求每行有人的座位求最小的x;
        MIN[Y[i]] = min(MIN[Y[i]], X[i]);

    node L = {INF, 1LL};

    for (int i = 2; i <= m; i++)
    {
        if (L.a != INF)
        {
            int x = L.a, y = L.b;
            //(x * (i - 1)) / y是找到维护的最大斜率在这一行的交点
            //将直线的式子写出来就可以很容易理解了
            // y=(b/a)x+c,这里c=1.
            if (x * (i - 1) % y == 0) //如果交点刚好为整数(及刚好在点上),那就-1
                h[i] = min(h[i], (x * (i - 1)) / y - 1);
            else
                h[i] = min(h[i], (x * (i - 1)) / y);
        }
        L = min(L, {MIN[i], i - 1}); //求最大的斜率
    }

    node R = {INF, 1LL};

    for (int i = m - 1; i >= 1; i--)
    {
        if (R.a != INF)
        {
            int x = R.a, y = R.b;
            // h[i] = min(h[i], (x * (m - i) - 1) / y);
            if (x * (m - i) % y == 0)
                h[i] = min(h[i], (x * (m - i)) / y - 1);
            else
                h[i] = min(h[i], (x * (m - i)) / y);
        }
        R = min(R, {MIN[i], m - i});
    }

    int res = 0;
    for (int i = 1; i <= m; i++)
    {
        h[i] = min(h[i], MIN[i] - 1);
        res += h[i];
    }
    cout << res << endl;
    return;
}

inline void solve()
{
    cin >> n >> m >> k >> q;

    for (int i = 1; i <= k; i++)
    {
        cin >> X[i] >> Y[i];
    }

    while (q--)
    {
        int p, x, y;
        cin >> p >> x >> y;
        X[p] = x, Y[p] = y;
        work();
    }

    return;
}
signed main()
{
    int _ = 1;
    // cin>> _;
    while (_--)
        solve();
    return 0;
}

2022牛客多校 C Grab the Seat!

C/C++/C#相关栏目本月热门文章