BZOJ 1182 - [Croatian2009]PLAHTE

#模拟

Published on 2016-10-15

描述

在一个无限大小的网格上有 $n(n\le {10}^5)$ 个矩形，给定每个矩形的坐标 $x_1,y_1,x_2,y_2$ 。在源点处有油渗出，时刻 $0$ 时覆盖 $(0,0)$ 格，之后每秒钟会向周围 8 个方向各延伸 $1$ 格。给定 $m(m\le {10}^5)$ 个询问，回答相应时刻时所有矩形被覆盖的面积之和。若同一格被不同矩形覆盖，则需要多次计算。没有矩形覆盖 $(0,0)$ 格。坐标的绝对值不超过 ${10}^6$ 。询问的时刻不超过 ${10}^6$ 。

分析

首先注意下这个坐标系，它是格子状的，别搞错了。由于没有格子覆盖 $(0, 0)$ ，那么我们的矩阵就变为了有限的几种：

在某个象限内（有可能包含了坐标轴）
与 $x$ 轴或 $y$ 轴相交。

对于第二种情况，我们可以将矩形拆为两个矩形，于是就变为了只有在某个象限内的矩形。又因为油的渗出是完全对称的，所以对于二三四象限的矩形，我们又可以将它们对称到第一象限去，现在只存在在第一象限内的矩形了。

我们的思路在于，造出一个事件序列，按照时间排序，有几种类型：

在时刻 $t$ ，查询当前时刻的面积和。
在时刻 $t$ ，加上一个增长速度：初速度为 $v_0$ ，加速度为 $a$ （第一秒覆盖 $v_0$ 个，第二秒覆盖 $v_0 + a$ 个...以此类推）。
在时刻 $t$ ，减去一个增长速度：速度为 $v$ ，加速度为 $a$ 。

对于类型三，速度 $v$ 不是加上这个速度时的初速度 $v_0$ ，而是 $v_0 + a \cdot (t_{\mathrm{start}} - t_{\mathrm{end}})$ ，即为其结束时候的速度。

显然对于两个相邻的时间的时间 $t_0, t_1$ ，即从第 $t_0 + 1$ 秒到第 $t_1$ 秒这一段时间内，它们的增长情况是相同的，所以我们可以一起结算，我们知道了在 $t_0$ 时刻的速度以及加速度，就能求出第 $t_0 + 1$ 秒到第 $t_1$ 的面积增长，求出来之后，将速度更新为在 $t_1$ 时刻的速度。

所以问题很明确，对于矩形 $(x_1,y_1,x_2,y_2)\;x_1,y_1,x_2,y_2 \ge 0$ ，将它的面积增长情况表示为事件。不妨设 $x_1\ge y_1$ ，否则根据对称性，将矩形关于 $y = x$ 做翻转，答案不会变化。

下面事件涉及到对时间的处理，每个人习惯的方式不一样，我只说思路，大家可以按照喜欢的方式处理（我的处理方法是，时间都是在某一时刻发生的，而油扩散的过程，是在一秒的时间中慢慢发生的）：第一次拥有速度的时刻，是在我们的油碰到矩形的下壁的时刻，这时候初速度为 $y_1 - x_1 + 1$ ，分为两种情况：如果 $y_1 - x_1 + 1$ 大于矩形的宽 $x_2 - x_1 + 1$ ，那么直接以固定的速度 $x_2 - x_1 + 1$ 增长，一直到碰到上壁为止。否则以 $y_1 - x1 + 1$ 的初速度， $2$ 的加速度增长，一直到碰到右壁或者上壁，无论先碰到谁，之后的速度都是恒定的。

说着很麻烦，画个图就很容易理解。容易发现事件的个数是 $O(n + m)$ 的，我们的时间瓶颈在于给事件排序，所以总复杂度： $O((n + m)\log(n + m))$ 。

代码

//  Created by Sengxian on 2016/10/12.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1182 模拟
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int MAX_N = 100000 + 3, MAX_M = 100000 + 3;
const int CNT = 2;
const int as[CNT] = {0, 2};

struct event {
    int time, type;
    ll v;
    bool a;
    inline bool operator < (const event &ano) const {
        return time < ano.time || (time == ano.time && type < ano.type);
    }
} events[MAX_N * 8 + MAX_M];

int n, m, cnt = 0;

inline ll cal(ll v0, int a, int t) {
    return v0 + (ll)t * as[a];
}

void add(int x1, int y1, int x2, int y2) {
    if (x2 < x1 || y2 < y1) return;
    if (x1 < 0 && x2 > 0) { //包含 y 轴
        add(x1, y1, 0, y2);
        add(1, y1, x2, y2);
    } else if (y1 < 0 && y2 > 0) { //包含 x 轴
        add(x1, y1, x2, 0);
        add(x1, 1, x2, y2);
    } else {
        //归到第一象限
        if (x1 < 0) swap(x1, x2), x1 = -x1, x2 = -x2;
        if (y1 < 0) swap(y1, y2), y1 = -y1, y2 = -y2;
        //归到 x = y 的上方
        if (x1 > y1) swap(x1, y1), swap(x2, y2);
        if (x2 - x1 + 1 <= y1 - x1 + 1) { //一开始就盖过了
            events[cnt++] = (event){y1, 1, x2 - x1 + 1, 0};
            events[cnt++] = (event){y2 + 1, 2, x2 - x1 + 1, 0};
        } else {
            events[cnt++] = (event){y1, 1, y1 - x1 + 1, 1};
            if (x2 - x1 + 1 - (y1 - x1 + 1) <= y2 - y1 + 1 - 1) { //先碰到右壁
                events[cnt++] = (event){x2 + 1, 2, cal(y1 - x1 + 1, 1, x2 + 1 - y1), 1};
                events[cnt++] = (event){x2 + 1, 1, x2 - x1 + 1, 0};
                events[cnt++] = (event){y2 + 1, 2, x2 - x1 + 1, 0};
            } else { //先碰到上壁
                events[cnt++] = (event){y2 + 1, 2, cal(y1 - x1 + 1, 1, y2 + 1 - y1), 1};
                events[cnt++] = (event){y2 + 1, 1, y2 - y1 + 1, 0};
                events[cnt++] = (event){x2 + 1, 2, y2 - y1 + 1, 0};
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    for (int _ = 0, x1, y1, x2, y2; _ < n; ++_) {
        x1 = ReadInt(), y1 = ReadInt(), x2 = ReadInt(), y2 = ReadInt();
        add(x1, y1, x2, y2);
    }

    m = ReadInt();
    for (int i = 0; i < m; ++i) events[cnt++] = (event){ReadInt() + 1, 0, 0, 0};
    sort(events, events + cnt);

    ll ans = 0, v[CNT] = {0};
    int last = 0, num[CNT] = {0};

    for (int i = 0, t; i < cnt; ++i) {
        t = events[i].time - last;
        for (int j = 0; j < CNT; ++j) {
            ans += (2 * v[j] + (ll)as[j] * num[j] * (t - 1)) * t / 2;
            v[j] += (ll)as[j] * num[j] * t;
        }
        last = events[i].time;
        if (events[i].type == 0) {
            printf("%lld\n", ans);
        } else if (events[i].type == 1) v[events[i].a] += events[i].v, num[events[i].a]++; //速度开始
        else if (events[i].type == 2) v[events[i].a] -= events[i].v, num[events[i].a]--; //速度结束
    }
    return 0;
}

BZOJ 1195 - [HNOI2006]最短母串 Codeforces 724F - Uniformly Branched Trees

Sengxian's Blog

BZOJ 1182 - [Croatian2009]PLAHTE

描述

分析

代码