算法概念

普通莫队

带修莫队

回滚莫队

树上莫队

二次离线莫队

莫队好题

普通莫队

bitset + 暴力枚举

题目描述

给了一个长度为 \(n\) 的序列， 有 \(m\) 次操作，每次询问一个区间是否有两个数的差为 \(x\) ，或和
为 \(x\) ，或乘积为 \(x\) 。

思路

引用出题人的话术：

考虑对于减操作，用bitset来维护每个数是否出现过
这样就可以O( c / 64 )的查询区间是否有两个数差为x了，即得到区间的bitset a，( a & ( a << x ) ).count()
加操作同理，维护一个反的bitset即可
乘操作直接暴力枚举小的因数，是 \(O(\sqrt n)\) 的
用膜队维护区间的bitset，总复杂度为 \(O(m\times(\sqrt n+\frac{c}{64}))\)
其实除也可以做的。。。只是似乎有点麻烦

• bitset 存每个数是否出现, \(s1[i] = 1\) 表示 \(i\) 出现过
• 查询区间是否有两数差为 \(x\), 即 \(b - a=x\) ，即 (s1[a] & (s1[a] << x)).any()，
• 查询区间是否有两数和为 \(x\)，即 \(a + b = x\)，由于 bitset 不能存负数的值域，进行如下变换：
  \[z + y = x = N - (N - y) + z = x -> z - (N - y) = x - N -> (N - y) - z = N - x \]

• 所以两数和的答案就是 (s2 & (s1 << (N - x))).any() 或 (s1 & (s2 >> (N - x))).any()
• 查询乘积，直接暴力枚举因数，复杂度 \(\sqrt n\)

Solution

#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 1e5 + 10, bound = 1e5;
bool ans[N], fl;
bitset s1, s2;
int cnt[N], w[N], len, n, m;

int get(int x){
	return x / len;
}

struct Q{
	int op, l, r, x, id;
	bool operator < (const Q& q)const{
		int al = get(l), bl = get(q.l);
		if(al != bl) return al < bl;
		return r < q.r;
	}
}q[N];


void add(int v){
	if(cnt[v]++ == 0) s1[v] = s2[N - v] = true;
}

void del(int v){
	if(--cnt[v] == 0) s1[v] = s2[N - v] = 0;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> w[i];
	len = sqrt(n);
	for(int i = 1; i <= m; i++){
		int op, l, r, x;
		cin >> op >> l >> r >> x;
		q[i] = {op, l, r, x, i};
	}
	sort(q + 1, q + 1 + m);
	for(int i = 1, l = 1, r = 0; i <= m; i++){
		auto [op, ql, qr, x, id] = q[i];
		while(l > ql) add(w[--l]);
		while(l < ql) del(w[l++]);
		while(r < qr) add(w[++r]);
		while(r > qr) del(w[r--]);
		if(op == 1){
			if((s1 & (s1 << x)).any())
				ans[id] = true;
		}
		else if(op == 2){
			if((s2 & (s1 << (N - x))).any())
				ans[id] = true;
		}
		else{
			for(int j = 1; j * j <= x; j++)
				if(x % j == 0 && s1[j] && s1[x / j]){
					ans[id] = true;
					break;
				}
		}
	}
	for(int i = 1; i <= m; i++)
		ans[i] ? cout << "hana\n" : cout << "bi\n";
    return 0;
}

带修莫队

回滚莫队

树上莫队