Cptraser/ 二月 3, 2019/ 2019.1/ 0 comments

补一波以前没写的PPT题解
题面传送门

维护两个Bitset,一个表示x,一个表示N-x
对于询问和差为x只要暴力枚举即可O(\frac{N * M}{w})
对于询问积只要\sqrt{N}枚举即可

#include <cmath>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int V=1e5+5;

bitset<V>F,G;
int N,M,Size,L=1,R,A[V],Cnt[V],Be[V],Ans[V];
struct Query{
    int Opt,L,R,x,id;
    bool operator<(const Query&P)const{
        return Be[P.L]==Be[L]?(Be[L]&1?R>P.R:R<P.R):L<P.L;//奇偶块排序
    }
}Q[V];
int main()
{
    read(N),read(M),Size=sqrt(N);
    for(int i=1;i<=N;i++)read(A[i]),Be[i]=(i-1)/Size+1;
    for(int i=1;i<=M;i++)read(Q[i].Opt),read(Q[i].L),read(Q[i].R),read(Q[i].x),Q[i].id=i;
    sort(Q+1,Q+M+1);
    for(int i=1;i<=M;i++){
        while(L>Q[i].L)--L,++Cnt[A[L]],F[A[L]]=1,G[100000-A[L]]=1;
        while(R<Q[i].R)++R,++Cnt[A[R]],F[A[R]]=1,G[100000-A[R]]=1;
        while(L<Q[i].L){--Cnt[A[L]];if(!Cnt[A[L]])F.set(A[L],0),G.set(100000-A[L],0);++L;}
        while(R>Q[i].R){--Cnt[A[R]];if(!Cnt[A[R]])F.set(A[R],0),G.set(100000-A[R],0);--R;}
        if(Q[i].Opt==1)Ans[Q[i].id]=(F&(F>>Q[i].x)).any();
        if(Q[i].Opt==2)Ans[Q[i].id]=(F&(G>>(100000-Q[i].x))).any();
        if(Q[i].Opt==3){
            for(int k=1;k*k<=Q[i].x;k++)if(!(Q[i].x%k)){
                if(F[k]&&F[Q[i].x/k]){Ans[Q[i].id]=1;break;}
            }
        }
    }
    for(int i=1;i<=M;i++)puts(Ans[i]?"yuno":"yumi");
    return 0;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*