并不对劲的复健训练-p3674

超、凢脫俗 2023-08-17 16:46 64阅读 0赞

##### 题目大意 #####

给出序列$ a\_1,...,a\_n $ ( $ n\\leq10^5，a\\leq 10^5 $ )，有\$m\$ ( \$m\\leq 10^5\$)个以下三类询问：

(1)给出\$l,r,k\$(\$k\\leq 10^5\$)，问是否存在\$x,y\$使\$x\\in\[l,r\],y\\in\[l,r\],a\_x-a\_y=k\$  
(2)给出\$l,r,k\$(\$k\\leq 10^5\$)，问是否存在\$x,y\$使\$x\\in\[l,r\],y\\in\[l,r\],a\_x+a\_y=k\$  
(3)给出\$l,r,k\$(\$k\\leq 10^5\$)，问是否存在\$x,y\$使\$x\\in\[l,r\],y\\in\[l,r\],a\_x\\times a\_y=k\$

##### 题解 #####

发现\$a、k\$的值域较小，而且没有修改或强制在线，考虑莫队。  
维护表示每个值在当前区间中是否存在的bitset，记为\$c\$。  
对于(1)操作，将式子变形为\$a\_x=a\_y+k\$，判断\$(c<<k)| c\$中第\$k\$位是否为1  
对于(2)操作，将式子变形为\$a\_x=k-a\_y\$，发现\$-a\_y\$不好直接算，但是可以维护\$(10^5-a\_y)\$，使式子变为\$a\_x=(10^5-a\_y)-10^5+k\$，记\$(10^5-a\_y)\$为\$d\$，判断\$(d>>(10^5-k))|c\$中第\$k\$位是否为1  
对于(3)操作，难以变形，可以考虑把\$k\$拆成\$\\sqrt k\$个约数，判断\$\\sqrt k\$个约数中是否有存在于\$a\_l,...,a\_r\$的。这样听上去是 莫队的时间复杂度\$\\times \\sqrt k=n^2\$级别的。但是发现这么写的代码长这样：

rep i 1 to m
        移动左右端点;
        判断根号k个约数;

所以判断约数的 \$\\sqrt k\$和莫队的\$\\sqrt n\$是相加的关系。

##### 代码 #####

#include<algorithm>
    #include<bitset>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];k!=-1;k=nxt[k])
    #define maxn 100007
    #define maxk 100000
    #define LL long long
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    bitset<100001>now,pnow;
    int a[maxn],n,m,num[maxn],ans[maxn],blo=300;
    struct quest{int f,l,r,x,id;}q[maxn];
    bool cmp(quest x,quest y){return (x.l/blo==y.l/blo)?(x.r<y.r):(x.l<y.l);}
    void add(int id,int f)
    {
        num[a[id]]+=f;
        if(f==1&&num[a[id]]==1){now[a[id]]=1,pnow[maxk-a[id]]=1;}
        if(f==-1&&!num[a[id]]){now[a[id]]=0,pnow[maxk-a[id]]=0;}
    }
    int main()
    {
        n=read(),m=read();
        rep(i,1,n)a[i]=read();
        rep(i,1,m)q[i].f=read(),q[i].l=read(),q[i].r=read(),q[i].x=read(),q[i].id=i;
        int nowl=1,nowr=1;num[a[1]]=1,now[a[1]]=1,pnow[maxk-a[1]]=1;
        sort(q+1,q+m+1,cmp);
        rep(i,1,m)
        {
            while(nowl<q[i].l){add(nowl,-1),nowl++;}
            while(nowr>q[i].r){add(nowr,-1),nowr--;}
            while(nowl>q[i].l){nowl--,add(nowl,1);}
            while(nowr<q[i].r){nowr++,add(nowr,1);}
            if(q[i].f==1){if(((now<<q[i].x)&now).any())ans[q[i].id]=1;}
            else if(q[i].f==2){if(((pnow>>(maxk-q[i].x))&now).any())ans[q[i].id]=1;}
            else
            {
                int lim=sqrt(q[i].x);
                rep(j,1,lim)if(q[i].x%j==0&&now.test(j)&&now.test(q[i].x/j)){ans[q[i].id]=1;break;}
            }
        }
        rep(i,1,m)puts(ans[i]?"hana":"bi");
        return 0;
    }

##### 一些感想 #####

之前轻视bitset的人被bitset教做人了  
bitset常用操作：

#include<bitset>//bitset的头文件
    bitset<6342>a; //开一个下标从0~6341的bitset
    a[63]=1,a[42]=0,a.set(63,1),a.set(42,0),a.reset(42);//赋值
    a.set(),a.reset();//全变成1或全变成0
    ((a<<634)|(a>>23)).any();//bitset可以直接进行位运算，any()返回是否存在一位是1
    a.none(),a.all(),a.test(5);//是否任意一位都为0；是否任意一位都为1；是否第5位为1
    a.flip(32),a[32].flip();//翻转第32位
    a.flip();//翻转全部
    a.count(),a.size();//返回一共有几位是1；返回一共有几位
    a.to_string(),a.to_ulong(),a.to_ullong();//把bitset变成string；unsigned long；unsigned long long

转载于:https://www.cnblogs.com/xzyf/p/11532017.html