LP3674 小清新人渣的本愿 [卡常莫队]

ajcxsu
ajcxsu 2018年05月06日
  • 39 次阅读

Problem

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

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

保证输入皆为非负整数。

Solution

并没有想出做法,所以来对题解做个稍微详细点的解释。
本题要用到bitset,所以不知道的同学可以移步到博客中的bitset教程:https://acxblog.site/archives/bitset.html

用个100000位的bitset x,代表每个数。
那么询问1则等价于,询问是否存在a-b=c,即a=c+b
等价于x&(x<<c)是否大于0。

询问2则是询问是否存在a=-b+c
则用第二个bitset y,y里维护负数。
怎么做?我们令bitset的大小等于2NN=1e5),然后令N为0。每次插入一个数,就令x[N+c]=y[N-c]=1
于是第二个询问等价于x&(y<<c)

询问3暴力枚举约数,复杂度$O(\sqrt{n})$。

然而这样被卡掉了。
我们发现x,y的大部分空间都没有用上,于是考虑高效利用空间。
我们令x,y的大小重新变为N,然后假设y的最高位接在x后方,即类似一个循环数组。
那么插入操作变为:x[c]=y[N-c]=1。每次查询的时候要把y往左移c位,即往右移N-c位。
第二个询问变成了x&(y>>(N-c))

剩下的用莫队维护就行。

Code

// Code by ajcxsu
// Problem: hina

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
bitset<N> s1,s2;
struct Query { int opt, l, r, x, id; } q[N];
int be[N];
bool cmp(const Query &a, const Query &b) { return be[a.l]==be[b.l]?a.r<b.r:a.l<b.l; }
bool ans[N];
int cnt[N];

inline void revise(int x, int d) {
    if(cnt[x]==1 && d==-1) s1[x]=0, s2[N-x]=0;
    if(cnt[x]==0 && d==1) s1[x]=1, s2[N-x]=1;
    cnt[x]+=d;
}

int n,m,l,r;
int a[N];

template<typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    gn(n), gn(m);
    int unit=sqrt(n);
    for(int i=1;i<=n;i++) gn(a[i]), be[i]=i/unit+1;
    for(int i=0;i<m;i++) gn(q[i].opt),gn(q[i].l), gn(q[i].r), gn(q[i].x), q[i].id=i;
    sort(q,q+m,cmp);
    l=1, r=0;
    for(int i=0;i<m;i++) {
        while(l<q[i].l) revise(a[l], -1), l++;
        while(l>q[i].l) revise(a[l-1], 1), l--;
        while(r<q[i].r) revise(a[r+1], 1), r++;
        while(r>q[i].r) revise(a[r], -1), r--;

        if(q[i].opt==1) ans[q[i].id]=(s1&(s1<<q[i].x)).any();
        else if(q[i].opt==2) ans[q[i].id]=(s1&(s2>>(N-q[i].x))).any();
        else {
            for(int j=1;j*j<=q[i].x;j++)
                if(q[i].x%j==0) ans[q[i].id]|=s1[j]&s1[q[i].x/j];
        }
    }
    for(int i=0;i<m;i++) {
        if(ans[i]) putchar('h'),putchar('a'),putchar('n'),putchar('a');
        else putchar('b'),putchar('i');
        putchar('\n');
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol_luogu_p3674.html
本文采用 CC BY-NC-SA 3.0 协议进行许可