Persistent Bookcase
题目链接：http://codeforces.com/contest/707/problem/D
注释：略。
题解：
发现虽然$q\le 10^5$但是网格是$1000\times 1000$的，而且每次操作只会操作一行。
故此我们考虑按照行来搞。
想到每次暴力重新建一行，但是空间开不下，我们用$bitset$即可。
但是我们又面临一个问题，即：回到某一个时刻。
这个很难弄，最简单的支持可持久化的数据结构是主席树，所以我们对行建主席树。
每次修改操作我们都新开一个$bitset$，主席树的第$i$个叶子表示的是第$i$行对应哪一个$bitset$。
时间复杂度为$O(\frac{np}{32} +plogn)$。
代码：
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define N 400010
using namespace std;
bitset <1010 > b[N], mdl;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
int cnt = 0, rt[N];
struct Node {
int v;
int ls, rs;
}a[N * 30];
void update(int x, int val, int l, int r, int &p, int pre) {
p = ++cnt;
a[p] = a[pre];
if (l == r) {
a[p].v = val;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(x, val, l, mid, a[p].ls, a[pre].ls);
}
else {
update(x, val, mid + 1, r, a[p].rs, a[pre].rs);
}
}
int query(int x, int l, int r, int p) {
if (l == r) {
return a[p].v;
}
int mid = (l + r) >> 1;
if (x <= mid) {
return query(x, l, mid, a[p].ls);
}
else {
return query(x, mid + 1, r, a[p].rs);
}
}
int ans[N];
void build(int l, int r, int &p) {
if (!p) {
p = ++cnt;
}
if (l == r) {
a[p].v = l;
return;
}
int mid = (l + r) >> 1;
build(l, mid, a[p].ls), build(mid + 1, r, a[p].rs);
}
int main() {
// setIO("now");
int n = rd(), m = rd(), q = rd();
for (int i = 1; i <= m; i ++ ) {
// 1 << (i - 1)
mdl.set(i);
}
build(1, n, rt[0]);
int tmp = n;
for (int i = 1; i <= q; i ++ ) {
int opt = rd();
ans[i] = ans[i - 1];
if (opt == 1) {
int x = rd(), y = rd();
int z = query(x, 1, n, rt[i - 1]);
b[ ++ tmp] = b[z];
b[tmp].set(y);
ans[i] += b[tmp].count() - b[z].count();
update(x, tmp, 1, n, rt[i], rt[i - 1]);
}
else if (opt == 2) {
int x = rd(), y = rd();
int z = query(x, 1, n, rt[i - 1]);
b[ ++ tmp] = b[z];
b[tmp].reset(y);
ans[i] += b[tmp].count() - b[z].count();
update(x, tmp, 1, n, rt[i], rt[i - 1]);
}
else if (opt == 3) {
int x = rd();
int z = query(x, 1, n, rt[i - 1]);
b[ ++ tmp] = b[z];
b[tmp].flip();
b[tmp] = b[tmp] & mdl;
ans[i] += b[tmp].count() - b[z].count();
update(x, tmp, 1, n, rt[i], rt[i - 1]);
}
else {
int x = rd();
ans[i] = ans[x];
rt[i] = rt[x];
}
printf("%d\n", ans[i]);
}
return 0;
}