ZJOI2017 树状数组

Vexoben

Mar 12, 2019

It takes 8 minutes to read this article.

题目链接：ZJOI2017 树状数组

签到题都不会做，真是太菜了啊。

（刷新以获取数学公式）

题意

太长不想写了，点到UOJ里面看吧……

题解

直观猜测这个树状数组可能是维护后缀和的，本地打了个代码跑了跑发现确实是这样。

询问时真实答案是 $\sum_{i=l}^{r}a_i$ ，而算出来的是 $\sum_{i=l-1}^{r-1}a_i$ ，注意这里加法是膜 $2$ 意义下的，也即是 $xor$ ，所以只要算 $a_{l-1}+a_r$ 即可。

一开始想的是把一个询问看做一个平面上的点，点权是 $P[a_{l-1}=a_{r}]$ 。那么一个修改就是对平面上三个区域做矩形乘一个数，矩形加一个数。

~~发现自己并不会打这样的树套树~~

~~事实上大力对两个线段树都大力维护标记是可以做的，然而想题的时候误把空间复杂度算成 $O(n^2)了$~~

定义一个 $merge$ 函数。 $merge(x,y)$ 的值表示，将一个 $x$ 概率为 $1$ ， $1-x$ 概率为 $0$ 的变量以 $y$ 概率反转，它的值为 $1$ 的概率。

那么只要支持矩形 $merge$ 一个数就好了。

~~把以前的代码搬出来发现自己会打了~~

注意要特判 $l=1$ ，这时候答案会变成 $a_r + \sum_{i=1}^{n}a_i$

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;

template <typename T> void read(T &x) {
	int f = 0;
	R char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 - '0' + c;
	if (f) x = -x;
}

int n, m, ans;

int Qpow(int x, int p) {
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

int Inv(int x) {
	return Qpow(x, mod - 2);
}

void merge(int &x, int y) {
	x = (1LL * x * (mod + 1 - y) + 1LL * (mod + 1 - x) * y) % mod;
}

namespace SegTree2D {
	int tot;
	int ch[N * 400][2], tr[N * 400], rt[N << 2];

	void Update1(int &x, int l, int r, int ql, int qr, int v) {
		if (!x) x = ++tot, tr[x] = 0;
		if (ql <= l && r <= qr) {
			merge(tr[x], v);
			return;
		}
		int mid = (l + r) >> 1;
		if (mid >= ql) Update1(ch[x][0], l, mid, ql, qr, v);
		if (mid < qr) Update1(ch[x][1], mid + 1, r, ql, qr, v);
	}

	void Update2(int x, int l, int r, int ql, int qr, int qly, int qry, int v) {
		if (ql <= l && r <= qr) {
			Update1(rt[x], 0, n, qly, qry, v);
			return;
		}
		int mid = (l + r) >> 1;
		if (mid >= ql) {
			Update2(x << 1, l, mid, ql, qr, qly, qry, v);
		}
		if (mid < qr) {
			Update2(x << 1 | 1, mid + 1, r, ql, qr, qly, qry, v);
		}
	}

	void Query1(int x, int l, int r, int pos) {
		if (!x) return;
		merge(ans, tr[x]);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (mid >= pos) {
			Query1(ch[x][0], l, mid, pos);
		}
		if (mid < pos) {
			Query1(ch[x][1], mid + 1, r, pos);
		}
	}

	void Query2(int x, int l, int r, int qx, int qy) {
		Query1(rt[x], 0, n, qy);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (mid >= qx) {
			Query2(x << 1, l, mid, qx, qy);
		}
		if (mid < qx) {
			Query2(x << 1 | 1, mid + 1, r, qx, qy);
		}
	}
}
using namespace SegTree2D;

int main() {
	read(n); read(m);
	int cnt = 0;
	while (m--) {
		int opt, l, r;
		read(opt); read(l); read(r);
		if (opt == 1) {
			int p = Inv(r - l + 1); ++cnt;
			Update2(1, 0, n, l, r, l, r, p * 2 % mod);
			Update2(1, 0, n, 0, l - 1, l, r, p);
			if (r < n) {
				Update2(1, 0, n, l, r, r + 1, n, p);
			}
		}
		if (opt == 2) {
			ans = 1;
			Query2(1, 0, n, l - 1, r);
			if ((l == 1) && cnt & 1) ans = mod + 1 - ans;
			if (ans >= mod) ans -= mod;
			printf("%d\n", ans);
		}
	}
	return 0;
}