很容易想到可以它操作序列弄成有向图，果断深搜。但我开始竟然用了一种特醇的方法，每个书架做一次深搜，复杂度O(nq)，跑到57个test就不动了。看看代码吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bitset>
using namespace std; const int MAXOPT = 100005; struct OPT{
int opt, r, c;
}op[MAXOPT]; struct bits{
char s[125];
void init(){
for(int i = 0; i < 125; i++) s[i] = 0;
}
bool find(int k){
int p = k / 8;
int m = k % 8;
if(s[p] & (1<<m)) return true;
return false;
} void set(int k){
int p = k / 8;
int m = k % 8;
s[p] |= (1<<m);
} void reset(int k){
int p = k / 8;
int m = k % 8;
s[p] ^= (1<<m);
} void flip(){
for(int i = 0; i < 125; i++){
s[i] ^= (-1);
}
}
}; struct STATE{
bits st;
void init(){
st.init();
counts = 0;
}
int counts;
}; vector<int>nt[MAXOPT]; int ans[MAXOPT];
int n, m, q; void dfs(int pos, STATE iter, int sh){
int sz = nt[pos].size();
for(int k = 0; k < sz; k++){
ans[nt[pos][k]] += iter.counts;
dfs(nt[pos][k], iter, sh);
} while(op[pos + 1].opt != 4 && pos < q){
pos ++;
if(op[pos].r == sh){
if(op[pos].opt == 1){
if(!iter.st.find(op[pos].c - 1)){
iter.counts++;
iter.st.set(op[pos].c - 1);
}
}
else if(op[pos].opt == 2){
if(iter.st.find(op[pos].c - 1)){
iter.counts --;
iter.st.reset(op[pos].c - 1);
}
}
else {
iter.st.flip();
iter.counts = m - iter.counts;
}
}
ans[pos] += iter.counts;
int sz = nt[pos].size();
for(int k = 0; k < sz; k++){
ans[nt[pos][k]] += iter.counts;
dfs(nt[pos][k], iter, sh);
}
} } int main(){
int opt, r, c;
memset(ans, 0, sizeof(ans));
scanf("%d%d%d", &n, &m, &q);
for(int i = 0; i <= q; i++)
nt[i].clear(); for(int i = 1; i <= q; i++){
scanf("%d", &op[i].opt);
if(op[i].opt == 1 || op[i].opt == 2){
scanf("%d%d", &op[i].r, &op[i].c);
}
else {
scanf("%d", &op[i].r);
}
if(op[i].opt == 4){
nt[op[i].r].push_back(i);
}
}
for(int i = 1; i <= n; i++){
STATE iter;
iter.init();
ans[0] += iter.counts;
dfs(0, iter, i);
} for(int i = 1; i <= q; i++){
printf("%d\n", ans[i]);
} return 0;
}
后来想到，一次操作只动一个书架，深搜之后把原来的状态还原回去就可以啦，复杂度O(q)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bitset>
using namespace std; const int MAXOPT = 100005; int state[1005][1005]; int n, m, q; struct operation{
int op, r, c;
}op[MAXOPT];
int ans[MAXOPT];
vector<int> nt[MAXOPT]; void dfs(int u){
int sz = nt[u].size();
for(int i = 0; i < sz; i++){
int v = nt[u][i];
if(op[v].op == 1){
int pre = state[op[v].r][op[v].c];
if(!pre){
state[op[v].r][op[v].c] = 1;
ans[v] = ans[u] + 1;
}
else ans[v] = ans[u];
dfs(v);
state[op[v].r][op[v].c] = pre;
}
else if(op[v].op == 2){
int pre = state[op[v].r][op[v].c];
if(pre){
state[op[v].r][op[v].c] = 0;
ans[v] = ans[u] - 1;
}
else ans[v] = ans[u];
dfs(v);
state[op[v].r][op[v].c] = pre;
}
else if(op[v].op == 3){
int c = 0;
for(int k = 1; k <=m; k++){
if(state[op[v].r][k]) c++;
state[op[v].r][k] ^= 1;
}
ans[v] = ans[u] - c + m - c;
dfs(v); for(int k = 1; k <=m; k++){
state[op[v].r][k] ^= 1;
} }
else{
ans[v] = ans[u];
dfs(v);
}
}
} int main(){ scanf("%d%d%d", &n, &m, &q);
memset(ans, 0, sizeof(ans));
memset(state, 0, sizeof(state));
for(int i = 1; i <= q; i++){
scanf("%d", &op[i].op);
if(op[i].op == 1 || op[i].op == 2){
scanf("%d%d", &op[i].r, &op[i].c);
}
else{
scanf("%d", &op[i].r);
}
if(op[i].op == 4) nt[op[i].r].push_back(i);
else nt[i - 1].push_back(i);
} dfs(0); for(int i = 1; i <= q; i++)
printf("%d\n", ans[i]); return 0;
}