题解：AT_abc461_e [ABC461E] E-liter

· · 题解

大脑拒绝考虑初始状态

调试半个钟头怒失此题

遂写题解

题意：

对于 N \times N 的全白网格，有两种操作：

  1. 将第 R 行所有格子变黑。

  2. 将第 C 列所有格子变白。

对于 Q 次这种操作，在每次操作后输出当前黑格总数。

分析：

分析简单情况

首先涂黑时，有两种情况：

  1. 这一行之前没有被任何涂黑操作涂黑过，直接增加了 N 个黑格。
  2. 这一行之前被涂黑操作 A 涂黑过，此时理应不产生贡献。但假如在 A 之后进行了 m 次不重复的涂白操作，那么第 A 行中对应的这 m 列都会涂白，减少了 A 产生的黑格。此时我们再次涂黑这一行时，就会把这些减少的黑格补回来，总黑格数加上 m。

大致如图：

涂白的时候，类似的也分两种情况：

  1. 这一列之前没有被任何涂白操作涂白过，那么这次操作会减少所有不重复的涂黑行各一个黑格。
  2. 这一列之前被 B 涂白过，并且在 B 之后我们又进行了 n 次不重复的涂黑操作，那么这次涂白操作就会对这 n 次不重复的涂黑操作各减少一个黑格，总黑格数减去 n。

总结规律

对于黑白各操作，我们可以总结一下：

  1. 如果涂白，那么从上一次在此处涂白到现在的时间内，共涂了多少次不重的黑行，就减少多少黑格，特别地，如果先前此处没有涂白过，则从最开始算起。
  2. 如果涂黑，那么从上一次在此处涂黑到现在的时间内，共涂了多少次不重的白列，就增加多少黑格，特别地，如果先前此处没有涂黑过，则增加 N 个黑格。

实现：

实现方案

这里我们发现，我们要知道各个时间段内的不重的涂黑、涂白操作的数量，那么每次操作的时候，可以在记录当前操作的同时，通过区间查询得到。不妨用两个以时间（第几次操作）为下标的树状数组来完成这一步。

此外，我们要知道先前在此处进行的涂黑或涂白操作的时间，可以用两个分别以下标为行号、列号的数组，然后依据规律模拟即可。

不难发现，这样的时间复杂度取决于查询次数和树状数组的时间复杂度，总共是 O(Q \log Q)，空间复杂度类似，均可过关。

代码实现

#include <iostream>
#include <vector>
struct FT // 树状数组
{
    std::vector<long long> tree;
    long long length = 0;
    FT(long long n)
    {
        length = n;
        tree.resize(n + 2, 0);
    }
    long long Lowbit(long long x)
    {
        return x & -x;
    }
    void Add(long long x, long long k)
    {
        for (long long i = x; i <= length; i += Lowbit(i))
            tree[i] += k;
    }
    long long Query(long long x)
    {
        if (x <= 0)
            return 0;
        long long sum = 0;
        for (long long j = x; j > 0; j -= Lowbit(j))
            sum += tree[j];
        return sum;
    }
    long long RangeQuery(long long l, long long r)
    {
        if (l > r)
            return 0;
        return Query(r) - Query(l - 1);
    }
};
int main()
{
    // 输入
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    long long n, q;
    std::cin >> n >> q;

    // 记录上一个在当前行/列进行的黑/白操作的时间，没有则默认-1
    std::vector<long long> blk(n + 1, -1), wht(n + 1, -1);
    // 记录各个时间黑/白操作分别进行了几次
    FT blkFT(q + 2), whtFT(q + 2);
    // 黑格数量
    long long blk_cnt = 0;

    for (long long t = 1; t <= q; t++)
    {
        long long op, x;
        std::cin >> op >> x;
        if (op == 1) // 涂黑操作
        {
            if (blk[x] == -1) // 第一次落在此处直接累加
                blk_cnt += n;
            else // 不是第一次落在此处，加上先前落在此处到现在，落下的白行数
            {
                blk_cnt += whtFT.RangeQuery(blk[x], t - 1);
                blkFT.Add(blk[x], -1); // 删去先前落在此处的情况（因为要求不重）
            }
            blkFT.Add(t, 1); // 记录落在此处的情况
            blk[x] = t;
        }
        else // 涂白操作类似
        {
            if ((wht[x] == -1))
                blk_cnt -=  blkFT.RangeQuery(0, t - 1);
            else    
            {
                blk_cnt -= blkFT.RangeQuery(wht[x], t - 1);
                whtFT.Add(wht[x], -1);
            }
            whtFT.Add(t, 1);
            wht[x] = t;
        }
        std::cout << blk_cnt << '\n';
    }
    return 0;
}