信阳建设企业网站,山西省城乡建设厅网站,电子商务公司简介模板,涪陵网站建设登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;有n*m盏灯#xff0c;q次操作#xff0c;每次可以将一整行或一整列的等打开或关闭
1n,m1e6;1q1e6
思路#xff1a;对于同一行或者同一列来说#xff0c;只要最后一次操作时开或者关#xff0…登录—专业IT笔试面试备考平台_牛客网
题目大意有n*m盏灯q次操作每次可以将一整行或一整列的等打开或关闭
1n,m1e6;1q1e6
思路对于同一行或者同一列来说只要最后一次操作时开或者关前面操作再多次也是无效操作所以每一行或每一列的最终情况至于那一行/列的最终操作有关与前面都无关所以我么就从最后一次操作开始可以无后效性的向前推我们记录每个行/列是否被访问过如果访问过一行/列那么就相当于整幅图少了一行/一列以内前面的操作无法影响他所以一边维护当前图的行列数一边维护答案即可
//#include__msvc_all_public_headers.hpp
#includebits/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;
}
