P4428 [BJOI2018]二进制

BJOI2018D1T2

不得不说人家BJOI的题一个个都是神仙,给人全新的做题体验---暴力出奇迹???

简要题意:

查询一段另一区间有多少个子区间满足重排之后能构成一个%3=0的二进制数

一看就不可做,20pts跑路, $O(n^2q)$

50pts...可能是每个询问我们都DP一次吗?然后DP可以 $n^2$ ??

好吧直接开正解

"传说中的动态dp？反正极其毒瘤就是了"

肯定先要推结论的,我一开始想直接找出0/1串的规律,挂了....

所以我们缩小到每个元素的性质而不是直接找整体的

对于1个1,如果他在奇数位置,那他会对答案贡献2,如果在偶数位置则会对答案贡献1,最后要求贡献%3=0

这个结论很显然对吧,因为 $2^{偶数}\equiv 1(mod 3)$ , $2^{奇数} \equiv 2(mod 3)$

那么我们考虑下合法的情况?....如果1的个数是偶数,那么一定可以,因为我们可以奇偶平分啊

如果1的个数是奇数?必须满足奇数的个数是偶数个数多至少3,为什么呢?否则我们奇偶配对后一定%3=1/2对吧

而大于3?如果是5,那么显然我们可以给偶数放个1,就又变成多3的情况,如果是4?你不觉得1的个数是偶数了吗?

所以综上所述,这个不太行,我们要补集转化

我们先想1的个数一定是奇数对吧,而且我们要满足能够构造出奇数比偶数多3?

1.只有1个1
2.奇数个1,而且0的个数小于等于1

否则我们有2个零?就一定可以构造出奇数比偶数多的假象

eg: 3个1,2个0 10101,7个1,2个0,101011111

这样我们就来快速找到一个区间的答案吧!动态DP啊!或者说DP过程分治化并记录?线段树!

我们要记录什么信息呢?包含不包含左右端点,4中情况第一维,有奇数个1还是偶数个,有0/1还是1/1,有0/1还是1/0,共四维,怎么转移啊?

所以我们把两个问题分开计数,然后最后减去算重的部分就好

第一个线段树上存这样的dp数组
$Dp_{i,j,k}$

其中i的定义和一开始的定义一样

j表示这个区间有奇数个1或者偶数个1

k表示这个区间有0个0或1个0

另一个线段树存这样的dp数组

$Dp_{i,j}$

i的定义还是和开始的定义一样，

j表示这个区间有0个1或者1个1

考虑第一个条件的转移我们需要对于每个节点维护:

前缀零的个数,后缀零的个数
包括了1个1的前缀和后缀的个数

那你会发现因为我们要计算跨过中间点的答案,所以就是左边0后缀0*右边前驱只有1个1的前缀+右边同理就是答案

然后再考虑第二种情况

设 $R_{i, j}$ 为线段后缀中满足 $0$ 的数量为 $i$ ， $1$ 的数量 $\bmod 2 = j$ 的数量。 $L$ 统计前缀，对称地是类似的。

那么你枚举 $A.R_{a, b}, B.L_{c, d}$ 考虑能否产生贡献：

若 $a+c \le 1$ 且 $b + d$ 为奇数，那么则可以产生对答案有他们俩乘积的贡献。

还有一个重复的就是1的个数和10/01的个数会被减重复对吧,这个直接用一个树状数组就能维护

然后没什么了,其他细节也不会,学个大概qwq

真的太难了

code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
typedef long long ll;
int n, mk, m;
int a[MAXN];

struct linetree1 {
	ll v[4 * MAXN][4][2][2];
	inline void merge(int p, int p1, int p2) { //非常恶心的merge函数
		for(int i = 0; i <= 1; i++)for(int k = 0; k <= 1; k++) //加法转移们
				v[p][0][i][k] = v[p1][0][i][k] + v[p2][0][i][k] + v[p1][2][i][k] + v[p2][1][i][k];
		for(int i = 0; i <= 1; i++)for(int k = 0; k <= 1; k++)v[p][1][i][k] = v[p1][3][i][k] + v[p1][1][i][k];
		for(int i = 0; i <= 1; i++)for(int k = 0; k <= 1; k++)v[p][2][i][k] = v[p2][3][i][k] + v[p2][2][i][k];
		for(int i = 0; i <= 1; i++)for(int k = 0; k <= 1; k++)v[p][3][i][k] = 0;
		for(int i = 0; i <= 1; i++) //乘法转移,这里for枚举p1,p2各选多少个0
			for(int j = 0; i + j <= 1; j++) //手动枚举了奇偶性的转移
				v[p][0][0][i + j] += v[p1][2][0][i] * v[p2][1][0][j] + v[p1][2][1][i] * v[p2][1][1][j],
									 v[p][0][1][i + j] += v[p1][2][0][i] * v[p2][1][1][j] + v[p1][2][1][i] * v[p2][1][0][j],
											 v[p][1][0][i + j] += v[p1][3][0][i] * v[p2][1][0][j] + v[p1][3][1][i] * v[p2][1][1][j],
													 v[p][1][1][i + j] += v[p1][3][0][i] * v[p2][1][1][j] + v[p1][3][1][i] * v[p2][1][0][j],
															 v[p][2][0][i + j] += v[p1][2][0][i] * v[p2][3][0][j] + v[p1][2][1][i] * v[p2][3][1][j],
																	 v[p][2][1][i + j] += v[p1][2][0][i] * v[p2][3][1][j] + v[p1][2][1][i] * v[p2][3][0][j],
																			 v[p][3][0][i + j] += v[p1][3][0][i] * v[p2][3][0][j] + v[p1][3][1][i] * v[p2][3][1][j],
																					 v[p][3][1][i + j] += v[p1][3][0][i] * v[p2][3][1][j] + v[p1][3][1][i] * v[p2][3][0][j];
	}
	inline void modify(int p, int l, int r, int pos) {
		if(r - l == 1) {
			if(a[r]) {
				v[p][3][1][0] = 1;
				v[p][3][0][1] = 0;
			} else {
				v[p][3][0][1] = 1;
				v[p][3][1][0] = 0;
			}
			return ;
		}
		int mid = (l + r) / 2;
		if(pos <= mid) {
			modify(p << 1, l, mid, pos);
		} else {
			modify(p << 1 | 1, mid, r, pos);
		}
		merge(p, p << 1, p << 1 | 1);
	}
	inline void query(int p, int l, int r, int dl, int dr) {
		if(dl == l && dr == r) {
			if(mk == 0) {
				for(int i = 0; i <= 3; ++i) {
					for(int j = 0; j <= 1; ++j) {
						for(int k = 0; k <= 1; ++k) {
							v[0][i][j][k] = v[p][i][j][k];
						}
					}
				}
				mk = 1;
			} else {
				for(int i = 0; i <= 3; ++i) {
					for(int j = 0; j <= 1; ++j) {
						for(int k = 0; k <= 1; ++k) {
							v[4 * n + 1][i][j][k] = v[0][i][j][k];
						}
					}
				}
				merge(0, 4 * n + 1, p);
			}
			return ;
		}
		int mid = (l + r) / 2;
		if(dl < mid) {
			query(p << 1, l, mid, dl, min(dr, mid));
		}
		if(mid < dr) {
			query(p << 1 | 1, mid, r, max(dl, mid), dr);
		}
	}
	inline ll cquery(int l, int r) {
		for(int i = 0; i <= 3; ++i) {
			for(int j = 0; j <= 1; ++j) {
				for(int k = 0; k <= 1; ++k) {
					v[0][i][j][k] = 0;
				}
			}
		}
		mk = 0;
		query(1, 0, n, l, r);
		ll ret = 0;
		for(int i = 0; i <= 3; ++i)ret += v[0][i][1][0] + v[0][i][1][1];
		return ret;
	}
	inline void build(int p, int l, int r) {
		if(r - l == 1) {
			// printf("%d %d %d %d\n", p, l, r, a[r]);
			if(a[r]) {
				v[p][3][1][0] = 1;
			} else {
				v[p][3][0][1] = 1;
			}
			return;
		}
		int mid = (l + r) / 2;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid, r);
		merge(p, p << 1, p << 1 | 1);
	}
} lt1;

struct linetree2 {
	ll v[4 * MAXN][4][2];
	inline void merge(int p, int p1, int p2) {
		for(int i = 0; i <= 1; ++i)v[p][0][i] = v[p1][0][i] + v[p2][0][i] + v[p1][2][i] + v[p2][1][i];
		for(int i = 0; i <= 1; ++i)v[p][1][i] = v[p1][3][i] + v[p1][1][i];
		for(int i = 0; i <= 1; ++i)v[p][2][i] = v[p2][3][i] + v[p2][2][i];
		for(int i = 0; i <= 1; ++i)v[p][3][i] = 0;

		for(int i = 0; i <= 1; i++)
			for(int j = 0; i + j <= 1; j++) {
				v[p][0][i + j] += v[p1][2][i] * v[p2][1][j];

				v[p][1][i + j] += v[p1][3][i] * v[p2][1][j];

				v[p][2][i + j] += v[p1][2][i] * v[p2][3][j];

				v[p][3][i + j] += v[p1][3][i] * v[p2][3][j];
			}
	}
	inline void modify(int p, int l, int r, int pos) {
		if(r - l == 1) {
			if(a[r]) {
				v[p][3][1] = 1;
				v[p][3][0] = 0;
			} else {
				v[p][3][0] = 1;
				v[p][3][1] = 0;
			}
			return ;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) {
			modify(p << 1, l, mid, pos);
		} else {
			modify(p << 1 | 1, mid, r, pos);
		}
		merge(p, p << 1, p << 1 | 1);
		return ;
	}

	inline void query(int p, int l, int r, int dl, int dr) {
		if(dl == l && dr == r) {
			if(mk == 0) {
				for(int i = 0; i <= 3; ++i)
					for(int j = 0; j <= 1; ++j) {
						v[0][i][j] = v[p][i][j];
					}
				mk = 1;
			} else {
				for(int i = 0; i <= 3; ++i)
					for(int j = 0; j <= 1; ++j) {
						v[4 * n + 1][i][j] = v[0][i][j];
					}
				merge(0, 4 * n + 1, p);
			}
			return ;
		}
		int mid = (l + r) >> 1;
		if(dl < mid) {
			query(p << 1, l, mid, dl, min(dr, mid));
		}
		if(mid < dr) {
			query(p << 1 | 1, mid, r, max(dl, mid), dr);
		}
	}
	inline ll cquery(int l, int r) {
		for(int i = 0; i <= 3; ++i) {
			for(int j = 0; j <= 1; ++j) {
				v[0][i][j] = 0;
			}
		}
		mk = 0;
		query(1, 0, n, l, r);
		ll ret = 0;
		for(int i = 0; i <= 3; ++i)ret += v[0][i][1];
		return ret;
	}
	inline void build(int p, int l, int r) {
		if(r - l == 1) {
			// printf("%d %d %d %d\n", p, l, r, a[r]);
			if(a[r]) {
				v[p][3][1] = 1;
			} else {
				v[p][3][0] = 1;
			}
			return ;
		}
		int mid = (l + r) / 2;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid, r);
		merge(p, p << 1, p << 1 | 1);

	}
} lt2;

struct treearray {
	int ta[MAXN];
	inline void c(int x, int t) {
		for(; x <= n; x += x & (-x))ta[x] += t;
	}
	inline int d(int x) {
		int r = 0;
		for(; x > 0; x -= x & (-x))r += ta[x];
		return r;
	}
	inline ll q(int l, int r) {
		return d(r) - d(l);
	}
} tr1, tr2;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	lt1.build(1, 0, n);
	lt2.build(1, 0, n);
	for(int i = 1; i <= n; ++i) {
		if(a[i]) {
			tr1.c(i, 1);
		}
		if(a[i]^a[i + 1] && i != n) {
			tr2.c(i, 1);
		}
	}
	scanf("%d", &m);
	for(int i = 1, t, l, r; i <= m; ++i) {
		scanf("%d", &t);
		// printf("%d?\n", i);
		//puts("QWQ");
		if(t == 1) {
			scanf("%d", &l);
			a[l] ^= 1;
			lt1.modify(1, 0, n, l);
			// puts("QAQ");

			lt2.modify(1, 0, n, l);
			// puts("QAQ");
			tr1.c(l, (a[l]) ? 1 : -1);
			if(l != n) {
				tr2.c(l, (a[l]^a[l + 1]) ? 1 : -1);
			}
			if(l != 1) {
				tr2.c(l - 1, (a[l - 1]^a[l]) ? 1 : -1);
			}
		} else {
			scanf("%d%d", &l, &r);
			ll len = r - l + 1;
			printf("%lld\n", len * (len + 1) / 2 - lt1.cquery(l - 1, r) - lt2.cquery(l - 1, r) + tr1.q(l - 1, r) + tr2.q(l - 1, r - 1));
			// printf("%d ", lt1.cquery(l - 1, r));
			// printf("%d ", lt2.cquery(l - 1, r));
			// printf("%d ", tr1.q(l - 1, r));
			// printf("%d ", tr2.q(l - 1, r - 1));
			// puts("QAQ");

		}
	}
	return 0;
}

夏晓光(loveJY)的博客

P5468 [NOI2019]回家路线