暑假牛客多校第四场 2023-7-28

dkdklcx / 2023-07-29 / 原文

未补完

L. We are the Lights

算法：反向构造

做法：
我们用c_on, r_on, c_off, r_off分别表示倒着推的行灯打开的集合、列灯打开的集合、列灯关闭的集合、行灯关闭的集合。倒着推时，我们先考虑on的情况。为了偷懒，我们就只考虑行的情况，因为列的情况实际上是一样的。
打开灯时，我们先查找r_on集合里是否之后要打开此行的灯，要打开就跳过，否则再找找r_off的集合中是否这行将被关闭，将被关闭也跳过。两种情况都不符合的话，我们就将这行加入r_on，并且加上这一行的最终打开的灯的数量，即ans += m - c_off.size() - c_on.size()。（注意：每一行要么出现在c_off，要么出现在c_on，因为如果这一行在从后往前推的过程中已经出现在了c_off里，那么现在你要打开这一行的灯是无意义的，因为未来你将关闭这行灯。如果这一行在从后往前推的过程中已经出现在了c_on里，那么现在你要关闭这一行的灯是无意义的，因为未来你要打开这一行的灯。）(另外，c_on.size()是为了防止重复加了某些灯。)
关闭灯时，我们先查找r_off集合里是否之后要关闭此行的灯，要关闭就跳过，否则再找找r_on的集合中是否这行将被打开，将被打开也跳过。两种情况都不符合的话，我们就将这行加入r_off，我们不需要删除任何数，因为我们再加灯的数量的时候就已经考虑了灯被关闭的影响。

code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 1000100;

int n, m, q;

struct W
{
	string x, st;
	int u;
}w[N];

void solve()
{
	LL ans = 0;
	cin >> n >> m >> q;
	set<int> c_on, r_on, c_off, r_off;
	
	for (int i = 0; i < q; i++)
	{
		int u;
		string x, st;
		cin >> x >> u >> st;
		w[i] = { x, st, u };
	}

	for (int i = q - 1; i >= 0; i--)
	{
		int u = w[i].u;
		string x = w[i].x, st = w[i].st;
		if (st == "off")
		{
			if (x == "row" && r_off.find(u) == r_off.end() && r_on.find(u) == r_on.end())r_off.insert(u);
			else if (x == "column" && c_off.find(u) == c_off.end() && c_on.find(u) == c_on.end())c_off.insert(u);
		}
		else if(st == "on")
		{
			if (x == "row")
			{
				if (r_off.find(u) != r_off.end())continue;
				else if (r_on.find(u) != r_on.end())continue;
				else
				{
					r_on.insert(u);
					ans += m - c_off.size() - c_on.size();
				}
			}
			else if(x == "column")
			{
				if (c_off.find(u) != c_off.end())continue;
				else if (c_on.find(u) != c_on.end())continue;
				else
				{
					c_on.insert(u);
					ans += n - r_off.size() - r_on.size();
				}
			}
		}
	}

	cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	solve();

	return 0;
}