bzoj4811 [Ynoi2017]由乃的OJ 树链剖分+贪心+二进制

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4811

题解

我现在为什么都写一题，调一天啊，马上真的退役不花一分钱了。

考虑这道题的弱化版 NOI2014 起床困难综合证的做法。

分成每一位来考虑，如果高位可以是 \(1\) 的话，那么尽量让高位为 \(1\)。

求出当前位为 \(0/1\) 时，最终得到的是 \(0\) 还是 \(1\)。因为要保证选的数小于 \(z\)，所以对于都可以得到 \(1\) 的情况，尽量选择 \(0\) 可以解除限制。

如果 \(z\) 这一位为 \(0\) 并且现在仍然被限制着，那么显然只能取 \(0\) 了。

到了树上，考虑用树链剖分维护线段树区间合并，可以得出我们刚刚需要的东西 —— 当前位为 \(0/1\) 时，最终得到的是 \(0\) 还是 \(1\)。

但是这样做是 \(O(mk\log^2n)\) 的，无法通过 dllxl 的数据。

考虑如何优化。

可以发现其实每一位是可以压在一起来同时操作的，所以用一个 \(64\) 位的二进制数来整体地表示这个区间的结果。

也就是 \(s_0\) 表示初值为 \(0\) 的结果，\(s_1\) 表示初值为 \(111111..111\) 的结果。

这样做就可以去掉一个 \(k\) 了，时间复杂度 \(O(m(k+\log^2n))\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I>

inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

#define lc o << 1

#define rc o << 1 | 1

const int N = 100000 + 7;

int n, m, k, dfc;

ull S;

int opt[N];

ull v[N];

int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

struct Node {

	ull s[2], r[2];

	inline Node() : s{0, S}, r{0, S} {}

	inline Node(const int &i) {

		int opt = ::opt[i];

		ull v = ::v[i];

		if (opt == 1) s[0] = 0, s[1] = v;

		else if (opt == 2) s[0] = v, s[1] = S;

		else s[0] = v, s[1] = (~v) & S;

		r[0] = s[0], r[1] = s[1];

	}

	inline Node(const ull &x, const ull &y) : s{x, y}, r{x, y} {}

} t[N << 2];

inline Node operator + (const Node &a, const Node &b) {

	Node ans;

	ans.s[0] = (a.s[0] & b.s[1]) | ((~a.s[0]) & b.s[0]);

	ans.s[1] = (a.s[1] & b.s[1]) | ((~a.s[1]) & b.s[0]);

	ans.r[0] = (b.r[0] & a.r[1]) | ((~b.r[0]) & a.r[0]);

	ans.r[1] = (b.r[1] & a.r[1]) | ((~b.r[1]) & a.r[0]);

	// dbg("******* %llu, %llu;    %llu, %llu;     %llu, %llu\n", a.s[0], a.s[1], b.s[0], b.s[1], ans.s[0], ans.s[1]);

	return ans;

}

inline Node operator - (const Node &a) {

	Node ans;

	ans.s[0] = a.r[0], ans.s[1] = a.r[1];

	ans.r[0] = a.s[0], ans.r[1] = a.s[1];

	return ans;

}

inline void build(int o, int L, int R) {

	if (L == R) return t[o] = Node(pre[L]), (void)0;

	int M = (L + R) >> 1;

	build(lc, L, M), build(rc, M + 1, R);

	t[o] = t[lc] + t[rc];

}

inline void qadd(int o, int L, int R, int x) {

	if (L == R) return t[o] = Node(pre[L]), (void)0;

	int M = (L + R) >> 1;

	if (x <= M) qadd(lc, L, M, x);

	else qadd(rc, M + 1, R, x);

	t[o] = t[lc] + t[rc];

}

inline Node qsum(int o, int L, int R, int l, int r) {

	if (l <= L && R <= r) return t[o];

	int M = (L + R) >> 1;

	if (r <= M) return qsum(lc, L, M, l, r);

	if (l > M) return qsum(rc, M + 1, R, l, r);

	return qsum(lc, L, M, l, r) + qsum(rc, M + 1, R, l, r);

}

inline Node qry(int x, int y) {

	Node ans1, ans2;

	while (top[x] != top[y]) {

		if (dep[top[x]] > dep[top[y]]) {

			ans1 = qsum(1, 1, n, dfn[top[x]], dfn[x]) + ans1;

			x = f[top[x]];

		} else {

			ans2 = qsum(1, 1, n, dfn[top[y]], dfn[y]) + ans2;

			y = f[top[y]];

		}

	}

	// dbg("x = %d, y = %d, dfn: %d %d\n", x, y, dfn[x], dfn[y]);

	if (dep[x] < dep[y]) ans2 = qsum(1, 1, n, dfn[x], dfn[y]) + ans2;

	else ans1 = qsum(1, 1, n, dfn[y], dfn[x]) + ans1;

	ans1 = (-ans1) + ans2;

	return ans1;

}

inline ull solve(int x, int y, ull z) {

	Node a = qry(x, y);

	// dbg("a.s[0] = %llu, a.s[1] = %llu, S = %llu, **** %llu\n", a.s[0], a.s[1], S, 9571068480616515248ull | 16544127868907869972ull);

	// dbg("*** a.s[0] = %llu, a.s[1] = %llu\n", (qry(2, 2)).s[0], (qry(2, 2)).s[1]);

	ull ans = 0, lim = 1;

	for (int i = k - 1; ~i; --i) {

		// dbg("%llu, %llu %llu\n", (z >> i) & 1, ((a.s[0] >> i) & 1), ((a.s[1] >> i) & 1));

		if ((!lim || ((z >> i) & 1)) && !((a.s[0] >> i) & 1) && ((a.s[1] >> i) & 1)) ans |= 1ull << i;

		else ans |= (1ull << i) & a.s[0], lim = lim && !((z >> i) & 1);//, dbg("i = %d\n", i);

	}

	// ull ans2 = 0;

	// for (int i = 0; i <= z; ++i) {

	//     ull cnt = 0;

	//     for (int j = k - 1; ~j; --j) cnt += a.s[(i >> j) & 1] & (1ull << j);

	//     smax(ans2, cnt);

	// }

	return ans;

}

inline void dfs1(int x, int fa = 0) {

	dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;

	for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);

}

inline void dfs2(int x, int pa) {

	top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;

	if (!son[x]) return; dfs2(son[x], pa);

	for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);

}

inline void work() {

	dfs1(1), dfs2(1, 1), build(1, 1, n);

	while (m--) {

		int opt, x, y;

		ull z;

		read(opt), read(x), read(y), read(z);

		if (opt == 2) ::opt[x] = y, v[x] = z, qadd(1, 1, n, dfn[x]);

		else printf("%llu\n", solve(x, y, z));

	}

}

inline void init() {

	read(n), read(m), read(k);

	if (k < 64) S = (1ull << k) - 1;

	else S = -1;

	// dbg("k = %d, S = %llu, %llu\n", k, (1ull << (k - 0)), 1ull << 64);

	for (int i = 1; i <= n; ++i) read(opt[i]), read(v[i]);

	int x, y;

	for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj4811 [Ynoi2017]由乃的OJ 树链剖分+贪心+二进制

题目传送门

题解

最新文章

热门文章