题目描述

见原题

样例

见原题

算法1

$O( min(n,m) )$

时间复杂度

这个算法理论的最坏情况是n==m==2e3，y老师的是n*m，但跑下来只比y老师的代码块60ms~100ms

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e6 + 10;

int row[N], col[N];
int n, m, k;
int add_r, add_c;

int main()
{
    cin >> n >> m >> k;

    add_r = m;              
    add_c = n;              

    while (k -- )
    {
        char op[2];
        int x;
        scanf ("%s%d", op, &x);

        if (*op == 'R') 
        {
            if (row[x]) add_c ++;
            else add_c --;

            row[x] = !row[x];       //初始全为0，也就是没涂;
        }                           //每涂一次就是取反;
        if (*op == 'C')
        {
            if (col[x]) add_r ++;
            else add_r --;

            col[x] = !col[x];   
        }
    }

    int res = 0;

    //这里应该判断n和m谁大,谁小就遍历谁,但是实操发现快不了多少;
    // if (n < m)

    for (int i = 1; i <= n; i ++ )  //统计一共有几个黑块;
        if (!row[i]) res += add_r;  //如果这一行没有被涂色,那么就有add_r个黑块;
        else res += m - add_r;      //如果被涂色，那么就有add_r个金块;

    // else
    // for (int i = 1; i <= m; i ++ )//这个循环和上个循环是完全等价的;    
    //     if (!col[i]) res += add_c;
    //     else res += n - add_c;

    // printf ("%d %d %d \n", add_r, add_c, res);//调试代码;

    //统计row或col,就能完全统计;
    cout << n * m - res << endl;

    return 0;
}