欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj4810 [Ynoi2017]由乃的玉米田

程序员文章站 2022-06-29 21:49:19
...

Description


由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。
由乃认为玉米田不美,所以她决定出个数据结构题

这个题是这样的:
给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是
否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1
,2,3选出的这两个数可以是同一个位置的数
bzoj4810 [Ynoi2017]由乃的玉米田

定义c为每次的x和ai中的最大值,ai >= 0,每次的x>=2n,m,c <= 100000

来自 https://www.lydsy.com/JudgeOnline/problem.php?id=4810

Solution


发现我不会在线做,那就考虑怎么离线
如果没有区间的限制可以用bitset数组w1记录出现了那些数字,数组w2则是w1反过来

差为x就满足(w1>>x)&w1不全为0。因为第i位代表有一个i,右移之后第i位代表有一个i-x
和位x就满足(w2<<(c-x))&w1不全为0。因为w2的第i位代表有一个c-i,左移之后第i位代表有一个c-(c-x)-I
乘积为x就枚举因数,这样只需要枚举到n

Code


#include <stdio.h>
#include <algorithm>
#include <bitset>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=100005;

struct Q {int opt,l,r,x,id;} q[N];

std:: bitset <N> w1,w2,tmp;

int ans[N],bct[N],a[N],size,max,sq;

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

bool cmp1(Q a,Q b) {
    return (a.l/size)<(b.l/size)||(a.l/size)==(b.l/size)&&(a.r<b.r);
}

bool cmp2(Q a,Q b) {
    return a.id<b.id;
}

void change(int x,int v) {
    int tmp=max-x;
    if (bct[x]==0&&v==1) {
        w1[x]=w2[tmp]=1;
    } else if (bct[x]==1&&v==-1) {
        w1[x]=w2[tmp]=0;
    }
    bct[x]+=v;
}

int query(Q q) {
    if (q.opt==2) {
        tmp=((w2>>(max-q.x))&w1);
        return (tmp.count());
    }
    if (q.opt==1) {
        tmp=((w1<<q.x)&w1);
        return (tmp.count());
    }
    rep(i,1,sq) {
        if (q.x%i==0&&w1[i]&&w1[q.x/i]) return true;
    }
    return false;
}

int main(void) {
    int n=read(),m=read();
    size=ceil(sqrt(n));
    rep(i,1,n) a[i]=read();
    rep(i,1,m) {
        q[i]=(Q) {read(),read(),read(),read(),i};
        max=std:: max(max,q[i].x);
    }
    sq=sqrt(max);
    std:: sort(q+1,q+m+1,cmp1);
    int l=1,r=0;
    rep(i,1,m) {
        for (;r<q[i].r;) change(a[++r],1);
        for (;r>q[i].r;) change(a[r--],-1);
        for (;l<q[i].l;) change(a[l++],-1);
        for (;l>q[i].l;) change(a[--l],1);
        ans[q[i].id]=query(q[i]);
    }
    rep(i,1,m) if (ans[i]) puts("yuno");
    else puts("yumi");
    return 0;
}
相关标签: bzoj