Codeforces Round 368 D.Persistent Bookcase

Wings 收录于类别 ACM

2021-01-21 2021-01-21 约 375 字预计阅读 2 分钟次阅读条评论

给你一个$n \times m$的01矩阵, 初始全0, 支持四种操作:

将 $(i,j)$ 变成1

将 $(i,j)$ 变成0

将第 $i$ 行的数字全部零一翻转

回到第 $k$ 次操作后的状态

进行 $q$ 次操作, 每次操作后输出当前矩阵1的个数

$1 \le n, m \le 10^3, 1 \le q \le 10^5$

有回到 $k$ 次操作, 考虑可持久化数据结构.

对一个序列可持久化可以用主席树, 对一个矩阵就不好搞了.

把每一行用bitset存一下, 就变成序列了.

bitset.count() 返回1的个数, bitset.flip() 反转.

因为 bitset 要指定大小, 就会出现指定的大小大于$m$的情况, 翻转以后只能考虑后一段, 此时直接 count() 显然错误. 可以用一个后 $m$ 位全1的bitset去与一下反转以后的bitset.

复杂度$O((n + k) \log n)$

cpp

const int MAXN = 1e3+10;
const int MAXQ = 1e5+10;
const int MAXM = (MAXN << 2) + MAXQ * 11;

int n, m, q;
bitset<MAXN> limit;

namespace HJTTree {
	int idx = 0, root[MAXQ];

	struct Node {
		int l, r, mid, lch, rch, val;
		bitset<MAXN> bit;
	} tree[MAXM];

	int build(int l, int r) {
		int u = ++idx;
		tree[u] = Node{l, r, (l+r)>>1, 0, 0, 0};
		tree[u].bit.reset();
		if (l < r) {
			tree[u].lch = build(l, tree[u].mid);
			tree[u].rch = build(tree[u].mid + 1, r);
		}
		return u;
	}

	void init() {
		root[0] = build(1, n);
	}

	void push_up(int u) {
		tree[u].val = tree[tree[u].lch].val + tree[tree[u].rch].val;
	}

	int update(int pre, int pos, int c, int d) {
		int u = ++idx;
		tree[u] = tree[pre];
		if (tree[u].l == tree[u].r) {
			tree[u].bit[c] = d;
			tree[u].val = tree[u].bit.count();
		}
		else {
			if (pos <= tree[u].mid)
				tree[u].lch = update(tree[pre].lch, pos, c, d);
			else
				tree[u].rch = update(tree[pre].rch, pos, c, d);
			push_up(u);
		}
		return u;
	}

	int flip(int pre, int pos) {
		int u = ++idx;
		tree[u] = tree[pre];
		if (tree[u].l == tree[u].r) {
			tree[u].bit.flip();
			tree[u].bit &= limit;
			tree[u].val = tree[u].bit.count();
		}
		else {
			if (pos <= tree[u].mid)
				tree[u].lch = flip(tree[pre].lch, pos);
			else
				tree[u].rch = flip(tree[pre].rch, pos);
			push_up(u);
		}
		return u;
	}

	int query(int i) {
		return tree[root[i]].val;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	HJTTree::init();
	limit.reset();
	for (int i = 1; i <= m; i++)
		limit[i] = 1;
	for (int i = 1; i <= q; i++) {
		int op, x, y;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d%d", &x, &y);
			HJTTree::root[i] = HJTTree::update(HJTTree::root[i-1], x, y, 1);
			printf("%d\n", HJTTree::query(i));
		}
		else if (op == 2) {
			scanf("%d%d", &x, &y);
			HJTTree::root[i] = HJTTree::update(HJTTree::root[i-1], x, y, 0);
			printf("%d\n", HJTTree::query(i));
		}
		else if (op == 3) {
			scanf("%d", &x);
			HJTTree::root[i] = HJTTree::flip(HJTTree::root[i-1], x);
			printf("%d\n", HJTTree::query(i));}
		else {
			scanf("%d", &x);
			HJTTree::root[i] = HJTTree::root[x];
			printf("%d\n", HJTTree::query(i));
		}
	}
	return 0;
}

还有离线的操作树做法, 有空学一下.