Submission #76483004

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXQ = 3e5 + 5;

int n, q;
int tree[2][MAXQ];
int lastRow[MAXQ], lastCol[MAXQ];

void add(int op, int x, int v)
{
    x++; // 时间从 0 开始，所以树状数组下标整体 +1
    while (x <= q + 1)
    {
        tree[op][x] += v;
        x += x & -x;
    }
}

int sum(int op, int x)
{
    x++;
    int res = 0;
    while (x > 0)
    {
        res += tree[op][x];
        x -= x & -x;
    }
    return res;
}

// 统计时间 <= x 的数量
int count_leq(int op, int x)
{
    return sum(op, x);
}

// 统计时间 < x 的数量
int count_less(int op, int x)
{
    if (x == 0) return 0;
    return sum(op, x - 1);
}

// 统计时间 > x 的数量
int count_greater(int op, int x)
{
    return n - count_leq(op, x);
}

signed main()
{
    cin >> n >> q;

    // 初始时刻 0，所有行、列都还没操作过
    add(0, 0, n); // 行的最后操作时间
    add(1, 0, n); // 列的最后操作时间

    int ans = 0;

    for (int t = 1; t <= q; t++)
    {
        int op, x;
        cin >> op >> x;

        if (op == 1)
        {
            // 把第 x 行涂黑
            int old = lastRow[x];

            // 这行原来有多少黑格：lastCol < old
            int before = count_less(1, old);

            // 现在这行全部变黑，一共有 n 个黑格
            ans += n - before;

            add(0, old, -1);
            add(0, t, 1);
            lastRow[x] = t;
        }
        else
        {
            // 把第 x 列涂白
            int old = lastCol[x];

            // 这一列原来有多少黑格：lastRow > old
            int before = count_greater(0, old);

            ans -= before;

            add(1, old, -1);
            add(1, t, 1);
            lastCol[x] = t;
        }

        cout << ans << '\n';
    }

    return 0;
}

Submission Info

Judge Result