慕容琳的后花园
慕容琳的后花园
洛谷#P3674#小清新人渣的本愿

小清新人渣的本愿

给定一个长度为 n 的数组 A ,有三种询问:
1.询问是否存在 A_i+A_j=x(i,j \in [l,r])
2.询问是否存在 A_i-A_j=x(i,j \in [l,r])
3.询问是否存在 A_i×A_j=x(i,j \in [l,r])

解法

我们使用莫队来解这道题
对于减法, A_i-A_j=x 化简为 A_i=A_j+x
维护一个bitset存区间内有的值,等价于s&(s<<x)存在一个 1
对于加法, A_i+A_j=x 化简为 A_i-(N-A_j)=x-N
和减法一样,维护一个bitset存 N-x 是否出现即可, N 取最大值
对于乘法,暴力枚举因子即可

ac代码

#include<bits/stdc++.h>
using namespace std;
bitset<100010>bi,bii;
int n,m,K,a[100010],to[100010],cnt[100010],ans[100010];
struct node
{
    int opt,l,r,x,id;
    void init(int i){scanf("%d%d%d%d",&opt,&l,&r,&x),id=i;}
    bool operator<(const node&a)const{return to[l]==to[a.l]?r<a.r:l<a.l;}
}q[100010];
void add(int x){if(cnt[x]++==0)bi[x]=1,bii[100000-x]=1;}
void del(int x){if(--cnt[x]==0)bi[x]=0,bii[100000-x]=0;}
int main()
{
    scanf("%d%d",&n,&m),K=sqrt(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),to[i]=(i-1)/K+1;
    for(int i=1;i<=n;i++)q[i].init(i);
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(q[i].l<l)add(a[--l]);
        while(q[i].r>r)add(a[++r]);
        while(q[i].l>l)del(a[l++]);
        while(q[i].r<r)del(a[r--]);
        if(q[i].opt==1)
        {
            if((bi&(bi<<q[i].x)).count())
                ans[q[i].id]=1;
        }
        else if(q[i].opt==2)
        {
            if((bi&(bii>>(100000-q[i].x))).count())
                ans[q[i].id]=1;
        }
        else if(q[i].opt==3)
        {
            int y=sqrt(q[i].x);
            for(int j=1;j<=y;j++)
                if(q[i].x%j==0&&bi[j]&&bi[q[i].x/j])
                    ans[q[i].id]=1;
        }
    }
    for(int i=1;i<=m;i++)
        if(ans[i])puts("hana");
        else puts("bi");
    return 0;
}
赞赏
首页      hgoi      洛谷#P3674#小清新人渣的本愿
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

洛谷#P3674#小清新人渣的本愿
小清新人渣的本愿 给定一个长度为 $n$ 的数组 $A$ ,有三种询问: 1.询问是否存在 $A_i+A_j=x(i,j \in [l,r])$ 2.询问是否存在 $A_i-A_j=x(i,j \in [l,r])$ 3.询问是否存在 $A_i×A_j=x(i,…
扫描二维码继续阅读
2019-11-09
功能