bitset && Luogu 3674 小清新人渣的本愿

bitset是什么

bitset是一个神奇的库,经常可以在你觉得过不了的时候帮你优化掉一个64或者32的常数,帮你成功卡过去

定义:
bitset < 10 > s

但是要注意,bitset中下标和我们理解的数字顺序是相反的,例如当你把s用一个字符串赋值的时候:

 string st = "100100";
 bitset < 10 > s(st);

下标和st中是反的,即s[0] = '0', s[1] = '0', s[2] = '1',以此类推,cout << s 的时候也是按照反下标的顺序输出的。

当你进行s << 1的操作的时候,是把每个数字的下标+1了,相当于把这个二进制数字左移一位(因为要反着看嘛)

这些操作的复杂度都是 \(O(N/w)\) (N是bitset的位数,w是机器字长)

有了这些东西就可以做题啦

bitsest优化DP

因为不是DP手所以决定瞎讲(bushi

当DP方程出现 \(dp(i, j) |= dp(i - 1, j - x)\)的时候,其实是一个一维的01数组向高位移动x位再或上原数据,那么我们就可以把这个01数组设位s,每次操作变成s = s | (s << x);
这个转移的复杂度是 \(O(N / w)\) 的。

Luogu 3674 小清新人渣的本愿

这道题才是重点
首先离线的话很容易想到莫队,但是这个的转移完全不是 \(O(1)\) 的,不同询问之间转换异常困难。
于是可以用 bitset 来做,首先要明确一点,bitset 优化的并不是转移的过程,转移必须是 \(O(1)\) 的,不然时间就不够用了,所以转移部分的时间复杂度是 \(O(n^{3/2})\),bitset 优化的是每次得出答案的过程,即得到答案这一部分的复杂度是 \(O({n*m}/w)\),两部分加起来,复杂度可以接受。

那么具体怎么做呢

  • 对于减法,这种是最简单的,维护一个值域大小的 bitset,每一位表示数字 i 有没有在 [L, R] 的区间内,这个转移显然是 \(O(1)\) 的,然后在莫队中每次把区间挪完,开始计算答案的时候,可以发现答案就是 s & (s<<x)的1的个数,因为两个数字如果差为 x,则一个数字加上x之后就等于另一个数字,这样计算不会重复也不会遗漏。
  • 对于加法,同样维护一个值域大小的 bitset,因为a + b = x相当于a = -b + x,所以第 i 位表示数字 -i + N有没有出现过(+N是为了让值为正),之后再用s & (s >> (N - x))来把它变成-b+x。
  • 对于乘法,直接 \(O(√N)\) 枚举因数就行了。

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int unit, a[N], cnt[N];
struct node {
    int opt, l, r, num, id;
    bool operator < (const node &x) const {
      return l / unit == x.l / unit
            ? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r)) : l < x.l; 
  }
} Ask[N];
bitset < N > s, s2; 
inline void Del(int x) {
    cnt[a[x]]--;
    if (!cnt[a[x]])	s[a[x]] = 0, s2[N - a[x]] = 0;
}

inline void Add(int x) {
    cnt[a[x]]++; s[a[x]] = 1, s2[N - a[x]] = 1;
}
bool ans[N];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	unit = sqrt(m);
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d%d", &Ask[i].opt, &Ask[i].l, &Ask[i].r, &Ask[i].num), Ask[i].id = i;
	sort(Ask + 1, Ask + m + 1);
	int L = 1, R = 0;
	for (int i = 1; i <= m; i++) {
		while (L > Ask[i].l) Add(--L);
	    while (R < Ask[i].r) Add(++R);
		while (L < Ask[i].l) Del(L++);
		while (R > Ask[i].r) Del(R--);
		if (Ask[i].opt == 1)
			ans[Ask[i].id] = (s & (s << Ask[i].num)).any();
		else if (Ask[i].opt == 2)
			ans[Ask[i].id] = (s & (s2 >> (N - Ask[i].num))).any();
		else {
			bool flag = false;
			for (int j = 1; j * j <= Ask[i].num; j++)
				if (Ask[i].num % j == 0)
					if (s[j] && s[Ask[i].num / j])
						flag = true;
			ans[Ask[i].id] = flag;
		}
	}
	for (int i = 1; i <= n; i++)
		ans[i] ? puts("hana") : puts("bi");
	return 0;
}
上一篇:【Luogu】P4916 [MtOI2018]魔力环 题解


下一篇:luogu P6178 【模板】Matrix-Tree 定理