首页 > 代码库 > bzoj4810 [Ynoi2017]由乃的玉米田
bzoj4810 [Ynoi2017]由乃的玉米田
Description
由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。
由乃认为玉米田不美，所以她决定出个数据结构题
这个题是这样的：
给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1,2,3选出的这两个数可以是同一个位置的数
Input
第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作，l,r表示操作的区间，x表示这次操作的x
定义c为每次的x和ai中的最大值，ai >= 0，每次的x>=2n,m,c <= 100000
Output
对于每个询问，如果可以，输出yuno，否则输出yumi
Sample Input
5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4
Sample Output
yuno
yumi
yuno
yuno
yumi
正解：莫队算法+$bitset$。
这题坑点巨多，数据范围都没给全。。
我们考虑莫队算法，把询问排个序就行了。如何统计答案？如果是两个数相乘等于$x$的情况，我们直接暴力枚举因子就行了。如果是两个数相减等于$x$的情况，我们把每个数压到$bitset$上，直接看$a[i]$的那个$bitset$数组右移$x$位以后再与一下原数组，如果不为0那么显然是有解的。如果是加法的话，我们考虑用另一个$bitset$来压$b[i]$，其中$b[i]$表示$c-a[i]$，其中$c$为$a[i]$的最大值。那么只要$a[i]=b[j]+x-c$，那就是有解的。于是我们把这个$bitset$数组右移$c-x$位，再与$a$数组的$bitset$数组与一下就行了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <bitset>10 #include <cmath>11 #include <queue>12 #include <stack>13 #include <map>14 #include <set>15 #define inf (1<<30)16 #define N (1000010)17 #define il inline18 #define RG register19 #define ll long long20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)21 22 using namespace std;23 24 struct node{ int i,opt,l,r,x; }q[N];25 26 int cnt[N],bl[N],ans[N],a[N],b[N],n,m,mc,block;27 28 bitset <100010> f,g,h;29 30 il int gi(){31 RG int x=0,q=1; RG char ch=getchar();32 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();33 if (ch==‘-‘) q=-1,ch=getchar();34 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();35 return q*x;36 }37 38 il int cmp(const node &a,const node &b){39 if (bl[a.l]==bl[b.l]) return a.r<b.r;40 return bl[a.l]<bl[b.l];41 }42 43 il void add(RG int x){44 cnt[a[x]]++;45 if (cnt[a[x]]==1) f[a[x]]=1,g[b[x]]=1;46 return;47 }48 49 il void del(RG int x){50 cnt[a[x]]--;51 if (!cnt[a[x]]) f[a[x]]=0,g[b[x]]=0;52 return;53 }54 55 il int check(RG int opt,RG int x){56 if (opt==1){57 h=f,h>>=x,h&=f;58 if (h.count()) return 1;59 }60 if (opt==2){61 h=g,h>>=abs(mc-x),h&=f;62 if (h.count()) return 1;63 }64 if (opt==3){65 RG int lim=sqrt(x+1);66 for (RG int i=1;i<=lim;++i){67 if (x%i) continue;68 if (cnt[i] && cnt[x/i]) return 1;69 }70 }71 return 0;72 }73 74 il void work(){75 n=gi(),m=gi(),block=sqrt(n),mc=100002;76 for (RG int i=1;i<=n;++i)77 a[i]=gi(),b[i]=mc-a[i],bl[i]=(i-1)/block+1;78 for (RG int i=1;i<=m;++i)79 q[i].i=i,q[i].opt=gi(),q[i].l=gi(),q[i].r=gi(),q[i].x=gi();80 sort(q+1,q+m+1,cmp); RG int L=q[1].l,R=q[1].r;81 for (RG int i=L;i<=R;++i) add(i); ans[q[1].i]=check(q[1].opt,q[1].x);82 for (RG int i=2;i<=m;++i){83 while (L>q[i].l) add(--L);84 while (R<q[i].r) add(++R);85 while (L<q[i].l) del(L++);86 while (R>q[i].r) del(R--);87 ans[q[i].i]=check(q[i].opt,q[i].x);88 }89 for (RG int i=1;i<=m;++i)90 puts(ans[i] ? "yuno" : "yumi");91 return;92 }93 94 int main(){95 File("yn");96 work();97 return 0;98 }
bzoj4810 [Ynoi2017]由乃的玉米田
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。