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

Sample Output

yuno
yumi
yuno
yuno
yumi

Solution

先莫個隊，然后對值域開個$bitset$。

差相等就是$f$并上$f$右移$x$不為$0$。

和相等就是$f$并上翻轉的$f$右移$N-x$位不為$0$。

積的話就$sqrt$枚舉$x$的的因子然后查詢存在性就好了。

Code

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<bitset> 5 #include<cmath> 6 #include<algorithm> 7 #define N (100000) 8 using namespace std; 9 10 struct Que{int opt,l,r,x,id;}Q[N+1]; 11 int n,m,unit,opt,l,r,x,a[N+1],ID[N+1]; 12 int ans[N+9],Keg[N+9]; 13 bitset<N+1>f,g; 14 15 inline int read() 16 { 17 int x=0,w=1; char c=getchar(); 18 while (!isdigit(c)) {if (c=='-') w=-1; c=getchar();} 19 while (isdigit(c)) x=x*10+c-'0', c=getchar(); 20 return x*w; 21 22 } 23 24 void Ins(int p) 25 { 26 if (!Keg[a[p]]) f[a[p]]=1, g[N-a[p]]=1; 27 ++Keg[a[p]]; 28 } 29 30 void Del(int p) 31 { 32 --Keg[a[p]]; 33 if (!Keg[a[p]]) f[a[p]]=0, g[N-a[p]]=0; 34 } 35 36 bool check(int opt,int x) 37 { 38 if (opt==1) return (f&(f>>x)).any(); 39 if (opt==2) return (f&(g>>(N-x))).any(); 40 if (opt==3) 41 { 42 for (int i=1; i<=sqrt(x); ++i) 43 if (x%i==0 && f[i] && f[x/i]) return 1; 44 return 0; 45 } 46 } 47 48 bool cmp(Que a,Que b) 49 { 50 if (ID[a.l]==ID[b.l]) return a.r<b.r; 51 return ID[a.l]<ID[b.l]; 52 } 53 54 int main() 55 { 56 n=read(); m=read(); unit=sqrt(n); 57 for (int i=1; i<=n; ++i) ID[i]=i/unit; 58 for (int i=1; i<=n; ++i) a[i]=read(); 59 for (int i=1; i<=m; ++i) 60 { 61 opt=read(); l=read(); r=read(); x=read(); 62 Q[i]=(Que){opt,l,r,x,i}; 63 } 64 sort(Q+1,Q+m+1,cmp); 65 int l=1,r=0; 66 for (int i=1; i<=m; ++i) 67 { 68 while (l<Q[i].l) Del(l++); 69 while (l>Q[i].l) Ins(--l); 70 while (r<Q[i].r) Ins(++r); 71 while (r>Q[i].r) Del(r--); 72 ans[Q[i].id]=check(Q[i].opt,Q[i].x); 73 } 74 for (int i=1; i<=m; ++i) puts(ans[i]?"yuno":"yumi"); 75 }

轉載于:https://www.cnblogs.com/refun/p/10453209.html

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的BZOJ4810:[YNOI2017]由乃的玉米田(莫队,bitset)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。