洛谷 P3674 小清新人渣的本愿 [莫队 bitset]

时间：2022-09-20 05:47:25

传送门

题意：

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

题面太强啦！！！

感觉就是莫队，想了一下分块不好搞更坚定了莫队的信念

$a-b=x$，$a=x+b$，放在权值数组上就是b右移x位，$bitset$大法好

加法同理

乘法，总共就$\sqrt{N}$个约数....

感觉复杂度$O(\frac{N^2}{64} + N\sqrt{N})$不靠谱结果竟然A了...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

typedef long long ll;

const int N=1e5+, M=2e5+;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n, Q, a[N], op, l, r, x;

int block, m, pos[N];

struct meow{

    int l, r, x, type, qid;

    bool operator <(const meow &a) const {return pos[l]==pos[a.l] ? r<a.r : pos[l]<pos[a.l];}

}q[N];

int ans[N];

struct Meow{

    bitset<M> a, b, c;

    int cou[N];

    inline void add(int v) {

        cou[v]++;

        if(cou[v]==) a[v]=, b[v+N]=, c[-v+N]=;

    }

    inline void del(int v) {

        cou[v]--;

        if(cou[v]==) a[v]=, b[v+N]=, c[-v+N]=;

    }

    int Que(int type, int x) { //printf("Que %d %d\n",type,x);

        int ans=;

        if(type==) {

            if( (a & (a<<x)).any() ) ans=;

        }else if(type==) {

            if( (b & (c<<x)).any() ) ans=;

        }else {

            int m=sqrt(x);

            for(int i=; i<=m; i++) if(x%i == )

                if(cou[i] && cou[x/i]) {ans=; break;}

        }

        return ans;

    }

}A;

void modui(){

    int l=, r=;

    for(int i=; i<=Q; i++){

        while(r<q[i].r) r++, A.add(a[r]);

        while(r>q[i].r) A.del(a[r]), r--;

        while(l<q[i].l) A.del(a[l]), l++;

        while(l>q[i].l) l--, A.add(a[l]);

        ans[q[i].qid]= A.Que(q[i].type, q[i].x);

    }

}

int main(){

//    freopen("in","r",stdin);

    n=read(); Q=read();

    block=sqrt(n); m=(n-)/block+;

    for(int i=; i<=n; i++) a[i]=read(), pos[i]=(i-)/block+;

    for(int i=; i<=Q; i++)

        op=read(), l=read(), r=read(), x=read(), q[i]=(meow){l, r, x, op, i};

    sort(q+, q++Q);

    modui();

    for(int i=; i<=Q; i++) puts(ans[i] ? "hana" : "bi");

}

相关文章