P3674 小清新人渣的本愿（莫队+bitset）

Description

State

Input

Output

Solution

Code

Description

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

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

State

\(n, m, max(x, a[i])<=10^5\)
\(a[i]>=0, x >= 2\)

Input

? 5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4

Output

? hana
bi
hana
hana
bi

Solution

看到题目的第一眼感觉用一个数组觉可以解决，但是题目设计的比较妙


如果上一次是 \(1\) 操作，当前为 \(2\) 操作，区间都相同，那么该怎么办呢

这提示我们需要用一种复杂度极低的查询方式，可以利用 \(bitset\) 的与操作

1. \(bitset & (bitset << x)\) 查找新的集合中是否存在 \(1\)
2. \(a+b=x\) 其中 \(a,b\) 是在 \(bitset\) 中出现过的数，将起转化为\(N-a-b=N-x\)，也就是 \((N-b)-a=(N-x)\)，这样又变成了 \(1\) 的形式
3. 这个就比较套路了，枚举 \(x\) 的因子就可以了

Code

const int N = 1e5 + 5;
 
    int n, m;
    int a[N];
    struct Query
    {
        int l, r;
        int bel;
        int id, opt, x;
        bool operator<(Query o){
            return bel == o.bel ? r < o.r: l < o.l;
        }
        void read(){ 
            sd(opt), sdd(l, r), sd(x); 
        }
    }q[N];
    int block, vis[N];
    bool ans[N];
    bitset now, rev;

void mo()
{
    block = 3 * sqrt(n);
    for(int i = 1; i <= m; i ++){
        q[i].id = i;
        q[i].bel = q[i].l / block + 1;
    }
    sort(q + 1, q + 1 + m);
}

void add(int pos)
{
    int x = a[pos];
    vis[x] ++;
    now[x] = 1;
    rev[N - x] = 1; 
}

void del(int pos)
{
    int x = a[pos];
    vis[x] --;
    if(vis[x]) return ;
    now[x] = 0;
    rev[N - x] = 0;
}

signed main()
{
    while(~ sdd(n, m)){
        rep(i, 1, n) sd(a[i]);
        rep(i, 1, m) q[i].read();
        mo();
        int l = 1, r = 0;
        now = 0;
        rev = 0;
        for(int i = 1; i <= m; i ++){
            while(l > q[i].l) add(-- l);
            while(r < q[i].r) add(++ r);
            while(l < q[i].l) del(l ++);
            while(r > q[i].r) del(r --);
            // dbg(now[1]);
            if(q[i].opt == 1){
                ans[q[i].id] = ((now & (now << q[i].x))).any();
            }
            else if(q[i].opt == 2){
                ans[q[i].id] = ((rev & (now << N - q[i].x)).any());
            }
            else{
                for(int k = 1; k * k <= q[i].x; k ++){
                    if(q[i].x % k == 0 && now[k] && now[q[i].x / k]){
                        ans[q[i].id] = 1;
                        break;
                    }
                }
            }
        }
        rep(i, 1, m) puts(ans[i]? "hana": "bi");
    }
    return 0;
}