P3674 小清新人渣的本愿
lxl大爷的题，%%%%%
以及CSP rp++！！！
前言：
其实是这题的名字吸引了我，毕竟人渣的本愿里的角色我觉得多多少少都沾点，哪来的小清新啊。《人渣的本愿》，又名《只要是【】子，睡过了也没问题是吗》。
解析：
一个 bitset 的小技巧（亦或是一种套路？）。
区间询问，不带修改，可以离线，并且是毒瘤lxl的题，考虑莫队。
在常规的莫队维护桶之外，用 bitset 来维护区间中的数用没有出现过，考虑查询时维护答案。
对于减法操作，若当前序列中存在
\[a - b = x \]可移项得：
\[a = b + x \]设一个 bitset 为 \(s\)，则有 s[b] = true 且 s[b + x] = true，则相当于 \(s \operatorname{\And}(s << x)\) 中存在一个 \(1\)。
对于加法操作，若当前序列中存在
\[a + b = x \]我们设 \(b^{'} = N - b\)，其中 \(N\) 为一个常数，有：
\[a - b^{'} = a + b - N = x - N \]然后我们移项可得
\[a + (N - x) = N - b \]之后，仿照我们减法操作的处理形式：s[a] = true，同时 s[a + (N - x)] = true，即 \(s \And (s << (N - x))\) 存在一个 \(1\)。这时为了防止加减法操作相互影响，我们再开一个 bitset 维护下 \(N - b\) 出现过没有即可。
因为 bitset 不能维护负数（没有负下标），所以 \(N\) 要是一个极大值，让 \(N\) 顶着数据范围即可。
对于乘法操作，我们直接枚举，只有 \(\sqrt{n}\) 个约数，所以单次查询的复杂度是 \(O(\sqrt{n})\) 的，由于 bitset 自带 \(\frac{1}{w}\) 的常数，所以总复杂度是 \(O(\frac{nm}{w})\) 的，可以通过本题。
Code
#include<cmath>
#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m, siz, lim;
int num[MAXN];
int belong[MAXN], temp[MAXN], ans[MAXN];
bitset<MAXN> add, cut;
struct Question{
int opt, l, r, x, id;
}q[MAXN];
bool cmp(const Question &a, const Question &b){
if(belong[a.l] != belong[b.l]) return belong[a.l] < belong[b.l];
if(belong[a.l] & 1) return a.r < b.r;
return a.r > b.r;
}
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
void Add(int x){
++temp[x];
if(temp[x] == 1){
add[x] = 1;
cut[lim - x] = 1;
}
}
void Del(int x){
--temp[x];
if(temp[x] == 0){
add[x] = 0;
cut[lim - x] = 0;
}
}
void Modify(int l, int r){
for(register int i = 1; i <= m; i++){
while(l < q[i].l) Del(num[l++]);
while(l > q[i].l) Add(num[--l]);
while(r < q[i].r) Add(num[++r]);
while(r > q[i].r) Del(num[r--]);
int opt = q[i].opt, x = q[i].x;
if(opt == 1) ans[q[i].id] = (add & (add << x)).any();
else if(opt == 2) ans[q[i].id] = (cut & (add << (lim - x))).any();
else{
for(register int d = 1; d * d <= x; d++){
if(x % d != 0) continue;
if(add[d] && add[x / d]){
ans[q[i].id] = 1;
break;
}
}
}
}
}
void init(){
siz = sqrt(n);
for(register int i = 1; i <= siz; i++){
int st = n / siz * (i - 1) + 1;
int ed = n / siz * i;
for(register int j = st; j <= ed; j++)
belong[j] = i;
}
}
int main(){
n = read(), m = read();
for(register int i = 1; i <= n; i++)
num[i] = read();
lim = MAXN;
init();
for(register int i = 1; i <= m; i++){
q[i].opt = read();
q[i].l = read(), q[i].r = read(), q[i].x = read();
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp);
Modify(1, 0);
for(register int i = 1; i <= m; i++){
if(ans[i]) puts("hana");
else puts("bi");
}
return 0;
}