@loj - 3043@「ZJOI2019」线段树

@description@
@solution@
@accepted code@
@details@

@description@

九条可怜是一个喜欢数据结构的女孩子，在常见的数据结构中，可怜最喜欢的就是线段树。

线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中 tag 数组为懒标记：

其中函数 \(Lson(Node)\) 表示 \(Node\) 的左儿子，\(Rson(Node)\) 表示 \(Node\) 的右儿子。

现在可怜手上有一棵 \([1,n]\) 上的线段树，编号为 \(1\)。这棵线段树上的所有节点的 tag 均为 \(0\)。接下来可怜进行了 \(m\) 次操作，操作有两种：

\(1\ l\ r\)，假设可怜当前手上有 \(t\) 棵线段树，可怜会把每棵线段树复制两份（tag 数组也一起复制），原先编号为 \(i\) 的线段树复制得到的两棵编号为 \(2i-1\) 与 \(2i\)，在复制结束后，可怜手上一共有 \(2t\) 棵线段树。接着，可怜会对所有编号为奇数的线段树进行一次 \(\rm{Modify}(root,1,n,l,r)\)。
\(2\)，可怜定义一棵线段树的权值为它上面有多少个节点 tag 为 \(1\)。可怜想要知道她手上所有线段树的权值和是多少。

原题传送门。

@solution@

考虑每个结点的贡献。

观察伪代码，修改操作 [l, r] 导致结点 x 的 tag 可能改变的情况只有 3 种：

（1）[l, r] 不包含 x 的父结点，但包含 x。此时 x 的 tag 强制变为 1。

（2）[l, r] 不包含 x，但与 x 有交。此时 x 的 tag 强制变为 0。

（3）[l, r] 与 x 没有交，但与 x 的父结点有交。此时如果 x 的某祖先有 tag，则 x 也有 tag。

因此考虑 dp：定义 dp(0/1, 0/1, x) 表示 x 的祖先结点是否有 tag，x 本身是否有 tag，这 4 种情况对应的方案数。

可以做到 \(O(nm)\) 的 dp，获得 40 分的好成绩。

考虑优化。观察 dp 的转移，发现只有线段树上单点修改/子树修改，单点询问/子树询问。

直接维护一下线段树上的单点 dp值/转移矩阵与子树 dp值/转移矩阵即可。

可以把 \(4\times 4\) 的转移矩阵优化成 3 个元素的转移矩阵，这样会跑得快一些。

这样就可以 \(O(m\log n)\) 通过该题。

@accepted code@

#include <cstdio>

#include <algorithm>

using namespace std;

#define lch (x << 1)

#define rch (x << 1 | 1)

#define rep(i, x, n) for(int i=x;i<n;i++)

const int MAXN = 100000;

const int MOD = 998244353;

inline int add(int x, int y) {x += y; return x >= MOD ? x - MOD : x;}

inline int sub(int x, int y) {x -= y; return x < 0 ? x + MOD : x;}

inline int mul(int x, int y) {return (int)(1LL * x * y % MOD);}

namespace segtree{

	struct tag{

		int t00, t01, t11;

		friend tag operator * (const tag &a, const tag &b) {

			tag c;

			c.t00 = mul(a.t00, b.t00);

			c.t01 = add(mul(a.t00, b.t01), mul(a.t01, b.t11));

			c.t11 = mul(a.t11, b.t11);

			return c;

		}

	};

	struct state{

		int f[2][2];

		friend state operator * (const state &a, const tag &b) {

			state c;

			rep(i, 0, 2) {

				c.f[0][i] = mul(b.t00, a.f[0][i]);

				c.f[1][i] = add(mul(b.t11, a.f[1][i]), mul(b.t01, a.f[0][i]));

			}

			return c;

		}

		friend state operator + (const state &a, const state &b) {

			state c;

			rep(i, 0, 2) rep(j, 0, 2)

				c.f[i][j] = add(a.f[i][j], b.f[i][j]);

			return c;

		}

	};

	int le[8*MAXN + 5], ri[8*MAXN + 5], ans;

	state s[8*MAXN + 5], v[8*MAXN + 5]; tag tg[8*MAXN + 5]; bool vis[8*MAXN + 5];

	void pushup(int x) {

		if( le[x] == ri[x] ) s[x] = v[x];

		else s[x] = s[lch] + s[rch] + v[x];

	}

	void addtag(int x, tag k) {s[x] = s[x] * k, v[x] = v[x] * k, tg[x] = tg[x] * k, vis[x] = true;}

	void pushdown(int x) {

		if( !vis[x] ) return ;

		addtag(lch, tg[x]), addtag(rch, tg[x]);

		tg[x].t00 = tg[x].t11 = 1, tg[x].t01 = 0, vis[x] = false;

	}

	void build(int x, int l, int r) {

		le[x] = l, ri[x] = r, v[x].f[0][0] = 1;

		tg[x].t00 = tg[x].t11 = 1, tg[x].t01 = 0;

		if( l != r ) {

			int m = (l + r) >> 1;

			build(lch, l, m), build(rch, m + 1, r);

		}

		pushup(x);

	}

	void modify_segment(int x, int type) {

		if( le[x] == ri[x] ) return ;

		pushdown(x);

		int del = add(s[lch].f[0][1], s[lch].f[1][1]); ans = add(ans, del);

		del = add(s[rch].f[0][1], s[rch].f[1][1]); ans = add(ans, del);

		if( type == 1 )

			addtag(lch, (tag){1, 1, 2}), addtag(rch, (tag){1, 1, 2});

		else addtag(lch, (tag){2, 0, 2}), addtag(rch, (tag){2, 0, 2});

		pushup(x);

	}

	void modify_point(int x, int type) {

		if( type == 1 ) {

			int del = add(add(v[x].f[0][1], v[x].f[1][1]), add(v[x].f[0][0], v[x].f[1][0]));

			v[x].f[0][1] = add(v[x].f[0][1], del), ans = add(ans, del);

		}

		else if( type == 2 ) {

			int del = add(add(v[x].f[0][1], v[x].f[1][1]), add(v[x].f[0][0], v[x].f[1][0]));

			v[x].f[0][0] = add(v[x].f[0][0], del);

		}

		else if( type == 3 ) {

			int del = add(add(v[x].f[0][1], v[x].f[1][0]), v[x].f[1][1]);

			v[x].f[0][1] = add(v[x].f[0][1], del), ans = add(ans, del);

			v[x].f[0][0] = add(v[x].f[0][0], v[x].f[0][0]);

		}

		pushup(x);

	}

	void update(int x, int l, int r) {

		if( l <= le[x] && ri[x] <= r )

			modify_point(x, 1), modify_segment(x, 1);

		else {

			modify_point(x, 2);

			int m = (le[x] + ri[x]) >> 1; pushdown(x);

			if( r <= m )

				update(lch, l, r), modify_point(rch, 3), modify_segment(rch, 2);

			else if( l > m )

				update(rch, l, r), modify_point(lch, 3), modify_segment(lch, 2);

			else update(lch, l, r), update(rch, l, r);

			pushup(x);

		}

	}

};

int main() {

	int n, m; scanf("%d%d", &n, &m);

	segtree::build(1, 1, n);

	for(int i=1,op,l,r;i<=m;i++) {

		scanf("%d", &op);

		if( op == 1 )

			scanf("%d%d", &l, &r), segtree::update(1, l, r);

		else printf("%d\n", segtree::ans);

	}

}

@details@

不要像我一样还写了另一棵线段树维护原线段树的dfs序然后变成了丑陋的O(nlog^2n)。

本题还有更优美的解法：观察到某个点是否有 tag 与它祖先上是否有 tag 相互独立，于是我们可以分别维护一个点是否有 tag 的概率与它祖先是否有 tag 的概率。

这个做法好像常数小很多。不管了反正我的做法也过了。

巴特西

@loj - 3043@「ZJOI2019」线段树

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章