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;

}

巴特西

[CF707D]Persistent Bookcase_主席树_bitset

Persistent Bookcase

最新文章

热门文章