A – 迷宫

这道题挺好的，让我知道了线段树还有这样的操作。

考虑线段树维护一段区间行入口到行出口的最短路，大概的维护方法非常像 Floyd。也没啥好说的，看代码吧。

// A.cpp
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int MAX_N = 2e5 + 1, INF = 0x3f3f3f3f;

int n, m, q, org[6][MAX_N];

struct node
{
    int mp[6][6];
} nodes[MAX_N << 2];

void pushup(node &p, node &ls, node &rs)
{
    memset(p.mp, 0x3f, sizeof(p.mp));
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                p.mp[i][j] = min(p.mp[i][j], ls.mp[i][k] + rs.mp[k][j]);
    return;
}

void build(int l, int r, int p)
{
    memset(nodes[p].mp, 0x3f, sizeof(nodes[p].mp));
    if (l == r)
    {
        for (int i = 1; i <= n; i++)
            if (org[i][l])
                for (int j = i; j <= n; j++)
                    if (org[j][l])
                        nodes[p].mp[i][j] = nodes[p].mp[j][i] = j - i + 1;
                    else
                        break;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(nodes[p], nodes[lson], nodes[rson]);
}

void update(int qx, int l, int r, int p)
{
    memset(nodes[p].mp, 0x3f, sizeof(nodes[p].mp));
    if (l == r && l == qx)
    {
        for (int i = 1; i <= n; i++)
            if (org[i][l])
                for (int j = i; j <= n; j++)
                    if (org[j][l])
                        nodes[p].mp[i][j] = nodes[p].mp[j][i] = j - i + 1;
                    else
                        break;
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    pushup(nodes[p], nodes[lson], nodes[rson]);
}

node query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    if (qr <= mid)
        return query(ql, qr, l, mid, lson);
    if (mid < ql)
        return query(ql, qr, mid + 1, r, rson);
    node fa, lft = query(ql, qr, l, mid, lson), rgt = query(ql, qr, mid + 1, r, rson);
    pushup(fa, lft, rgt);
    return fa;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &org[i][j]);
    build(1, m, 1);
    while (q--)
    {
        int opt, a, b, c, d;
        scanf("%d%d%d", &opt, &a, &b);
        if (opt == 1)
            org[a][b] ^= 1, update(b, 1, m, 1);
        else
        {
            scanf("%d%d", &c, &d);
            if (b > d)
                puts("-1");
            else
            {
                node nd = query(b, d, 1, m, 1);
                if (nd.mp[a][c] == INF)
                    puts("-1");
                else
                    printf("%d\n", nd.mp[a][c] - 1);
            }
        }
    }
    return 0;
}

B – 猛汉王

这道题真毒瘤。

我们分别把有瓶子的和没瓶子的分为黑色点和白色点。整个问题就变成了：在一个图上，把一些无向边的方向进行标记，然后找出一种方案能让单向三角形最多，其中我们只需要求最大值就行了（当然了，最小值的求法是非常相似的）。

我们发现端点异色的边的方向跟 Manhattan 距离和参数 d 相关，所以我们可以尝试预处理一个数组cover[i]代表与点\(i\) Manhattan 距离小于\(d\)的点的个数，其中我们可以扩展一下，设cover[i, j]与\(i, j\)两点 Manhattan 距离均小于\(d\)的点的个数。最后，最大值的答案显然是：

\[ max_ans = \sum_{i, j \in White} max\{ cover[i] – cover[i, j], cover[j] – cover[i. j] \} \]

进行一定的变换：

\[ max_ans = \sum_{i, j\in White} max\{ cover[i], cover[j] \} – cover[i, j] \]

发现\(cover[i, j]\)其实就是对于每一个黑点可选的 Manhattan 距离小于\(d\)的白点个数：

\[ max_ans = \sum_{i, j\in White} max\{ cover[i], cover[j] \} – \sum_{u \in Black} {cover[u] \choose 2} \]

所以我们现在需要计算出\(cover[]\)来进行这个计算。直接求曼哈顿距离小于\(d\)的点数有点困难，我们考虑把一个点的坐标系进行「翻折」，从\((x, y) \to (x + y, x – y)\)。我们会发现，翻折坐标系之后，考虑两点之间的 Manhattan 距离就变成了考虑两点之间的「切比雪夫距离」（\(max\{|x_i – x_j|, |y_i – y_j|\}\)，发现变换坐标系之后带入满足绝对值不等式，也就是 Manhattan 距离的定义）。所以，围绕新的坐标，发现\(cover[i]\)等于以点\(i\)为中心半径为\(D\)的正方形内的点数，这就是扫描线经典问题了（POJ 2482），套上就行。

// B.cpp
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, d, tree[MAX_N << 2];
long long min_ans = 0, max_ans = 0, minusComb = 0;

vector<ll> mapping, xlist;

template <class T>
inline T read(T &x)
{
    T data = 0;
    int w = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        data = 10 * data + ch - '0', ch = getchar();
    return x = data * w;
}

inline int lowbit(int x) { return x & -x; }

void add(int x, int d)
{
    int siz = mapping.size();
    for (; x <= siz; x += lowbit(x))
        tree[x] += d;
}

int query(int x)
{
    int ans = 0;
    for (; x; x -= lowbit(x))
        ans += tree[x];
    return ans;
}

struct point
{
    ll x, y;
    bool operator<(const point &pt) const { return x < pt.x || (x == pt.x && y < pt.y); }
} pts1[MAX_N], pts2[MAX_N];

struct quad
{
    ll x, y, aff;
    bool operator<(const quad &qd) const { return x < qd.x; }
};
vector<quad> vec;

int cover[MAX_N];

int ripe(ll x) { return lower_bound(mapping.begin(), mapping.end(), x) - mapping.begin() + 1; }

void solve()
{
    memset(tree, 0, sizeof(tree));
    vec.clear(), xlist.clear(), mapping.clear();
    for (int i = 1; i <= m; i++)
    {
        vec.push_back(quad{pts2[i].x - d, pts2[i].y, 1});
        vec.push_back(quad{pts2[i].x + d + 1, pts2[i].y, -1});

        xlist.push_back(pts2[i].x - d), xlist.push_back(pts2[i].x + d + 1);

        mapping.push_back(pts2[i].y);
    }

    for (int i = 1; i <= n; i++)
    {
        xlist.push_back(pts1[i].x);
        mapping.push_back(pts1[i].y - d - 1), mapping.push_back(pts1[i].y + d);
    }

    sort(xlist.begin(), xlist.end()), sort(mapping.begin(), mapping.end());
    xlist.erase(unique(xlist.begin(), xlist.end()), xlist.end());
    mapping.erase(unique(mapping.begin(), mapping.end()), mapping.end());

    sort(vec.begin(), vec.end());
    int cur1 = 0, cur2 = 1;
    for (ll x : xlist)
    {
        while (cur1 < vec.size() && vec[cur1].x == x)
            add(ripe(vec[cur1].y), vec[cur1].aff), cur1++;
        while (cur2 <= n && pts1[cur2].x == x)
            cover[cur2] = query(ripe(pts1[cur2].y + d)) - query(ripe(pts1[cur2].y - d - 1)), cur2++;
    }

    sort(cover + 1, cover + 1 + n);

    for (int i = 1; i <= n; i++)
    {
        min_ans += 1LL * (n - i) * cover[i];
        max_ans += 1LL * (i - 1) * cover[i];
        minusComb += 1LL * (1LL * cover[i] * (cover[i] - 1) >> 1);
    }
}

int main()
{
    /*
    freopen("mhw.in", "r", stdin);
    freopen("mhw.out", "w", stdout);
    */
    read(n), read(m), read(d);
    for (int i = 1, x, y; i <= n; i++)
    {
        read(x), read(y);
        pts1[i].x = x + y, pts1[i].y = x - y;
    }
    for (int i = 1, x, y; i <= m; i++)
    {
        read(x), read(y);
        pts2[i].x = x + y, pts2[i].y = x - y;
    }
    sort(pts1 + 1, pts1 + 1 + n);
    sort(pts2 + 1, pts2 + 1 + m);

    solve();
    swap(n, m), swap(pts1, pts2);

    solve();

    printf("%lld %lld", min_ans - minusComb, max_ans - minusComb);
    return 0;
}