BZOJ 1182 - [Croatian2009]PLAHTE

Published on 2016-10-15

题目地址

描述

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

分析

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

  1. 在某个象限内(有可能包含了坐标轴)
  2. xx 轴或 yy 轴相交。

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

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

  1. 在时刻 tt,查询当前时刻的面积和。
  2. 在时刻 tt,加上一个增长速度:初速度为 v0v_0,加速度为 aa(第一秒覆盖 v0v_0 个,第二秒覆盖 v0+av_0 + a 个...以此类推)。
  3. 在时刻 tt,减去一个增长速度:速度为 vv,加速度为 aa

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

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

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

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

说着很麻烦,画个图就很容易理解。容易发现事件的个数是 O(n+m)O(n + m) 的,我们的时间瓶颈在于给事件排序,所以总复杂度:O((n+m)log(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;
}