牛客多校第四场 J 题题解

J Counting Fish Again

J 题题意：在第一象限含坐标轴的无穷大方格纸上，可以画一条斜率为 $-1-1$ 的线段 $(u_1,v_1)\to (u_2,v_2)(u\_1,v\_1)\; \backslash to\; (u\_2,v\_2)$，或者擦除已经有的一条线段，问每次操作后鱼的个数。鱼形状如下：

操作次数 $qq$ 满足 $q\le 1\times 10^{6}q\; \backslash leq\; 1\backslash times\; 10^6$。

解法：对于每一个截距的直线单独考虑，利用珂朵莉树的方法维护每条直线上的最长连续线段，只需要对每个最长连续线段所对应的鱼进行计数即可。注意到鱼尾和鱼身的连接点可以唯一确定一条鱼，因而对这一连接点进行讨论。

首先考虑鱼头朝下的情况。这种情况复杂在于鱼头可能会超出坐标格。假定鱼尾和鱼身的连接点 $PP$ 为 $(x_0,y_0)(x\_0,y\_0)$，此时所画斜线方程为 $l:x+y=Bl:x+y=B$，斜线线段为 $(u_1,v_1)\to (u_2,v_2)(u\_1,v\_1)\; \backslash to\; (u\_2,v\_2)$。考虑 $PP$ 关于 $ll$ 的对称点 $P^{\mathrm{\prime }}(x_1,y_1)P\text{'}(x\_1,y\_1)$ 有 $y_0-x_0=y_1-x_{1}y\_0-x\_0=y\_1-x\_1$，且 $x_1+y_1+x_0+y_0=2Bx\_1+y\_1+x\_0+y\_0=2B$，可得 $P^{\mathrm{\prime }}(B-y_0,B-x_0)P\text{'}(B-y\_0,B-x\_0)$。则鱼头 $QQ$ 和 $P^{\mathrm{\prime }}P\text{'}$ 的中点即为 $PP$，因而有 $Q(2x_0+y_0-B,2y_0+x_0-B)Q(2x\_0+y\_0-B,2y\_0+x\_0-B)$ 且满足 $QQ$ 在第一象限。因而 $2x_0+y_0\ge B,2y_0+x_0\ge B2x\_0+y\_0\; \backslash geq\; B,2y\_0+x\_0\; \backslash geq\; B$。此外还有限制 $x_0\in [u_1,u_2],y_0\in [v_1,v_2],x_0+y_0\le Bx\_0\; \backslash in\; [u\_1,u\_2],y\_0\; \backslash in\; [v\_1,v\_2],x\_0+y\_0\; \backslash leq\; B$。

考虑对于以上的限制进行计算合法的格点数。首先仅考虑 $x=u_1,y=v_2,x+y=Bx=u\_1,y=v\_2,x+y=B$ 围成的区域，点数为 ${\displaystyle \frac{1}{2}}(u_2-u_1)(u_2-u_1-1)\backslash dfrac\{1\}\{2\}(u\_2-u\_1)(u\_2-u\_1-1)$。接下来考虑 $2x+y=B2x+y=B$ 和 $x+2y=Bx+2y=B$。

对于 $2x+y=B2x+y=B$，情况如下：

$D(u_1,B-2u_1)D(u\_1,B-2u\_1)$，$E({\displaystyle \frac{B-v_2}{2}},v_2)E\backslash left(\backslash dfrac\{B-v\_2\}\{2\},v\_2\backslash right)$，因而 $\mathrm{\Delta }ADE\backslash Delta\; ADE$ 根据 $EE$ 是否为整点可以得到其覆盖点数为

1. $EE$ 整点：${\displaystyle \frac{1}{2}}(B-2u_1-v_2+2{)}^2\backslash dfrac\{1\}\{2\}(B-2u\_1-v\_2+2)^2$；
2. $EE$ 不是整点：${\displaystyle \frac{1}{2}}(B-2u_1-v_2+1)(B-2u_1-v_2+3)\backslash dfrac\{1\}\{2\}(B-2u\_1-v\_2+1)(B-2u\_1-v\_2+3)$。

同理 $x+2y=Bx+2y=B$ 的情况为 $D(u_1,{\displaystyle \frac{B-u_1}{2}})D\backslash left(u\_1,\backslash dfrac\{B-u\_1\}\{2\}\backslash right)$ ，$E(B-2v_2,v_2)E(B-2v\_2,v\_2)$。此时根据 $DD$ 是否为整点可以计算出 $\mathrm{\Delta }ADE\backslash Delta\; ADE$ 覆盖点数为

1. $DD$ 为整点：${\displaystyle \frac{1}{2}}(B-2v_2-u_2+2{)}^2\backslash dfrac\{1\}\{2\}(B-2v\_2-u\_2+2)^2$；
2. $DD$ 不为整点：${\displaystyle \frac{1}{2}}(B-2v_2-u_2)(B-2v_2-u_2+3)\backslash dfrac\{1\}\{2\}(B-2v\_2-u\_2)(B-2v\_2-u\_2+3)$。

接下来考虑两条线交叠的下方不规则区域：

将区域拆分为 $AFGHAFGH$ 和 $\mathrm{\Delta }GHE\backslash Delta\; GHE$。$GG$ 坐标为 $({\displaystyle \frac{B}{3}},{\displaystyle \frac{B}{3}})\backslash left(\backslash dfrac\{B\}\{3\},\backslash dfrac\{B\}\{3\}\backslash right)$，首先将 $GHGH$ 向右平移至横坐标为一整点后，计算出 $GHGH$ 的长 $B-2\lceil {\displaystyle \frac{B}{3}}\rceil +1B-2\backslash left\; \backslash lceil\; \backslash dfrac\{B\}\{3\}\backslash right\; \backslash rceil+1$ 后 $\mathrm{\Delta }GHE\backslash Delta\; GHE$ 部分和上面问题等同；同时，$GHAFGHAF$ 范围内的整点数可以由 $\mathrm{\Delta }FAI\backslash Delta\; FAI$ 中整点数目减去 $\mathrm{\Delta }GHI\backslash Delta\; GHI$ 中个数得到。或者使用 Pick 定理也可。

对于直线上侧的点，无限制，答案为 ${\displaystyle \frac{1}{2}}(u_2-u_1)(u_2-u_1-1)\backslash dfrac\{1\}\{2\}(u\_2-u\_1)(u\_2-u\_1-1)$。因而对于一条给定的线段都可以实现 $\mathcal{O}(1)\backslash mathcal\; O(1)$ 的计算合法的鱼数目。

插入一条边时，需要考虑 $(u_1,v_1)(u\_1,v\_1)$ 左侧是否有一条线段末端在 $(u_1,v_1)(u\_1,v\_1)$，右侧同理。首先进行延申，去除旧线段然后插入延申后的新线段。对删除，找到目标线段，该目标线段一定是完全覆盖删除段的。这时等效于先把目标线段删除，再插入两端未删除部分。总复杂度为珂朵莉树的 $\mathcal{O}(q\log q)\backslash mathcal\; O(q\; \backslash log\; q)$。

#include <bits/stdc++.h>
using namespace std;
long long ans;
const long long inf = 0x3f3f3f3fll;
class Chtholly
{
    long long sum;
    long long S(long long l, long long r)
    {
        if (l > r)
            return 0;
        long long ss = (sum + l + sum + r) * (r - l + 1) / 2;
        long long mod2 = 0;
        long long K = max(0ll, (r - l + 1) / 2 - 1);
        mod2 += K;
        l += K * 2;
        for (long long i = l; i <= r; i++)
            mod2 += (sum + i) % 2;
        return (ss - mod2) / 2;
    }
    long long cal(long long x, long long X)
    {
        long long res = 0;
        long long R = max({x, (X + 1) / 2, X + X - sum});
        if (x + x > (sum + x) / 2)
            res += S(x, R - 1);
        else
        {
            long long p = sum / 3;
            while (p + p < (sum + p) / 2)
                p++;
            while (p + p - 2 >= (sum + p - 1) / 2)
                p--;
            p = min(p, R);
            res += S(p, R - 1);
            if (p > x)
                res += (x + x + p - 1 + p - 1) * (p - x) / 2;
        }
        if (R <= X)
            res += X * (X - R + 1);
        long long len = X - x;
        return res + len * (len + 1) / 2 - (x + X) * (X - x + 1) / 2;
    }
    set<pair<long long, long long>> t;

public:
    void init(long long sum)
    {
        this->sum = sum;
    }
    void add(long long l, long long r)
    {
        auto it = t.lower_bound(make_pair(r, r));
        if (it != t.end() && it->first == r)
        {
            r = it->second;
            ans -= cal(it->first, it->second);
            t.erase(it);
        }
        it = t.lower_bound(make_pair(r, r));
        if (it != t.begin())
        {
            it = prev(it);
            if (it->second == l)
            {
                l = it->first;
                ans -= cal(it->first, it->second);
                t.erase(it);
            }
        }
        t.insert(make_pair(l, r));
        ans += cal(l, r);
    }
    void del(long long l, long long r)
    {
        auto it = prev(t.upper_bound({l, inf}));
        auto old = *it;
        ans -= cal(it->first, it->second);
        t.erase(it);
        if (old.first < l)
            add(old.first, l);
        if (old.second > r)
            add(r, old.second);
    }
};
int main()
{
    map<long long, Chtholly> t;
    int q, op;
    long long x1, x2, y1, y2;
    scanf("%d", &q);
    while(q--)
    {
        scanf("%d%lld%lld%lld%lld", &op, &x1, &y1, &x2, &y2);
        if (x1 > x2)
        {
            swap(x1, x2);
            swap(y1, y2);
        }
        long long sum = x1 + y1;
        if(t.count(sum) == 0)
            t[sum].init(sum);
        if (op == 1)
            t[sum].add(x1, x2);
        else
            t[sum].del(x1, x2);
        printf("%lld\n", ans);
    }
    return 0;
}