Problem

给你一个序列 a，长度为 n，有 m 次操作，每次询问一个区间是否可以选出两个数它们的差为 x，或者询问一个区间是否可以选出两个数它们的和为 x，或者询问一个区间是否可以选出两个数它们的乘积为 x ，这三个操作分别为操作 1,2,3

选出的这两个数可以是同一个位置的数

保证输入皆为非负整数。

Solution

并没有想出做法，所以来对题解做个稍微详细点的解释。
本题要用到 bitset，所以不知道的同学可以移步到博客中的 bitset 教程：https://pst.iorinn.moe/archives/bitset.html。

用个 100000 位的bitset x，代表每个数。
那么询问 1 则等价于，询问是否存在a-b=c，即a=c+b。
等价于x&(x<<c)是否大于 0。

询问 2 则是询问是否存在a=-b+c
则用第二个bitset y，y 里维护负数。
怎么做？我们令 bitset 的大小等于2N（N=1e5），然后令N为 0。每次插入一个数，就令x[N+c]=y[N-c]=1。
于是第二个询问等价于x&(y<<c)。

询问 3 暴力枚举约数，复杂度 $O(\sqrt{n})$。

然而这样被卡掉了。
我们发现x,y的大部分空间都没有用上，于是考虑高效利用空间。
我们令x,y的大小重新变为 N，然后假设 y 的最高位接在 x 后方，即类似一个循环数组。
那么插入操作变为：x[c]=y[N-c]=1。每次查询的时候要把 y 往左移 c 位，即往右移 N - c 位。
第二个询问变成了x&(y>>(N-c))。

剩下的用莫队维护就行。

Code

// Code by ajcxsu
// Problem: hina

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
bitset<N> s1,s2;
struct Query { int opt, l, r, x, id; } q[N];
int be[N];
bool cmp(const Query &a, const Query &b) { return be[a.l]==be[b.l]?a.r<b.r:a.l<b.l; }
bool ans[N];
int cnt[N];

inline void revise(int x, int d) {
    if(cnt[x]==1 && d==-1) s1[x]=0, s2[N-x]=0;
    if(cnt[x]==0 && d==1) s1[x]=1, s2[N-x]=1;
    cnt[x]+=d;
}

int n,m,l,r;
int a[N];

template<typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    gn(n), gn(m);
    int unit=sqrt(n);
    for(int i=1;i<=n;i++) gn(a[i]), be[i]=i/unit+1;
    for(int i=0;i<m;i++) gn(q[i].opt),gn(q[i].l), gn(q[i].r), gn(q[i].x), q[i].id=i;
    sort(q,q+m,cmp);
    l=1, r=0;
    for(int i=0;i<m;i++) {
        while(l<q[i].l) revise(a[l], -1), l++;
        while(l>q[i].l) revise(a[l-1], 1), l--;
        while(r<q[i].r) revise(a[r+1], 1), r++;
        while(r>q[i].r) revise(a[r], -1), r--;

        if(q[i].opt==1) ans[q[i].id]=(s1&(s1<<q[i].x)).any();
        else if(q[i].opt==2) ans[q[i].id]=(s1&(s2>>(N-q[i].x))).any();
        else {
            for(int j=1;j*j<=q[i].x;j++)
                if(q[i].x%j==0) ans[q[i].id]|=s1[j]&s1[q[i].x/j];
        }
    }
    for(int i=0;i<m;i++) {
        if(ans[i]) putchar('h'),putchar('a'),putchar('n'),putchar('a');
        else putchar('b'),putchar('i');
        putchar('\n');
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_p3674.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆