We are the Lights 2023牛客暑期多校训练营4-L

登录—专业IT笔试面试备考平台_牛客网

题目大意：有n*m盏灯，q次操作，每次可以将一整行或一整列的等打开或关闭

1<=n,m<=1e6;1<=q<=1e6

思路：对于同一行或者同一列来说，只要最后一次操作时开或者关，前面操作再多次也是无效操作，所以每一行或每一列的最终情况，至于那一行/列的最终操作有关，与前面都无关，所以我么就从最后一次操作开始可以无后效性的向前推，我们记录每个行/列是否被访问过，如果访问过一行/列，那么就相当于整幅图少了一行/一列，以内前面的操作无法影响他，所以一边维护当前图的行列数，一边维护答案即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int co[N], r[N];
bool visc[N], visr[N];
char op1[N];
int op2[N];
int main()
{int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= q; i++){string a, c;int b;cin >> a >> b >> c;if (a[0] == 'r'){r[b] = (c[1] == 'n' ? 1 : 0);//记录每一行最后一次操作是开还是关}else{co[b] = (c[1] == 'n' ? 1 : 0);}op1[i] = a[0];//记录操作顺序op2[i] = b;//记录每次操作的行列}ll ans = 0;ll cc = m, cr = n;for (int i = q; i >= 1; i--){if (op1[i] == 'r'){if (visr[op2[i]])continue;//每一行就访问一次visr[op2[i]] = 1;if(r[op2[i]])ans += cc;//每一行的贡献就是当前列数cr--;//处理完一行，行数-1}else{if (visc[op2[i]])continue;visc[op2[i]] = 1;if(co[op2[i]])ans += cr;cc--;}if(!cc&&!cr)break;}cout << ans << endl;return 0;
}