[Ynoi2017]由乃的玉米田

Time Limit: 30 Sec  Memory Limit: 256 MB

Submit: 917  Solved: 447

[][][]

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

HINT

 

Source

 

题解：一开始以为是数据结构题，然后想了好久，题目也有一个坑点，可以选两个同位置的数，就是可以选相同的数。

　　　然后对于乘法的话，根号枚举即可，对于加法减法怎么办，可以用bitset优化，因为值的数据范围不大，

　　　所以我们可以x-y=z,那么x这个bitset右移z位，判断一下，和原来有没有交即可，对于区间的话还是需要莫队一下的

　　　对于加法x+y=z，貌似可以向左移，但是这里转换了以下，换成c-y，然后，x右移 c-(c-y)=+y，所以就可以了，

　　　这样复杂度是呢n^2/32的，莫队是并列的不是嵌套。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 8 #define N 400007 9 using namespace std;10 inline int read()11 {12 int x=0,f=1;char ch=getchar();13 while(!isdigit(ch)){ if(ch=='-')f=-1;ch=getchar();}14 while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}15 return x*f;16 }17 18 int n,m,c,blo;19 int a[N],b[N],bel[N],ans[N],num[N];20 struct Node21 {22 int opt,l,r,x,id;23 friend bool operator<(Node x,Node y)24 {25 if (bel[x.l]==bel[y.l]) return x.r
            
             f,g,h;30 31 void add(int x)32 {33 num[a[x]]++;34 if (num[a[x]]==1)35 {36 f[a[x]]=1;37 g[b[x]]=1;38 }39 }40 void del(int x)41 {42 num[a[x]]--;43 if (num[a[x]]==0)44 {45 f[a[x]]=0;46 g[b[x]]=0;47 }48 }49 bool query(Node w)50 {51 if (w.opt==3)52 {53 int up=sqrt(w.x);54 for (int i=1;i<=up;i++)55 if (w.x%i==0) if (num[i]&&num[w.x/i]) return true;56 }57 else if (w.opt==2)58 {59 h=g;60 h>>=(c-w.x);61 h&=f;62 if (h.count()) return true;63 }64 else65 {66 h=f;67 h>>=w.x;68 h&=f;69 if (h.count()) return true;70 }71 return false;72 }73 void solve_modui()74 {75 int l=1,r=0;76 for (int i=1;i<=m;i++)77 {78 for (;r
             
              q[i].r;r--)del(r);80 for (;l
              
               q[i].l;l--)add(l-1);82 ans[q[i].id]=query(q[i]);83 }84 for (int i=1;i<=m;i++)85 if (ans[i]) puts("yuno");86 else puts("yumi");87 }88 int main()89 {90 n=read(),m=read(),blo=2*sqrt(n),c=100007;91 for (int i=1;i<=n;i++)92 a[i]=read(),b[i]=c-a[i],bel[i]=(i-1)/blo+1;93 for (int i=1;i<=m;i++)94 q[i].opt=read(),q[i].l=read(),q[i].r=read(),q[i].x=read(),q[i].id=i;95 sort(q+1,q+m+1);96 solve_modui();97 }