4810: [Ynoi2017]由乃的玉米田

Time Limit: 30 Sec  Memory Limit: 256 MB

Submit: 815  Solved: 399

[][][]

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

 

考虑莫队

把a[i]和maxn-b[i]压到bitset上

加减用bitset左移查询

乘除直接暴力

……

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 #include
             
               8 #define maxn 100005 9 using namespace std;10 int read() {11 int x=0,f=1;char ch=getchar();12 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;13 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';14 return x*f;15 }16 int belong[maxn],size;17 struct data {18 int t,x,y,ask,id,ans;19 bool operator <(const data tmp) {20 if(belong[x]==belong[tmp.x]) return belong[x]%2?y>tmp.y:y
              
               t2.y:t1.y
               
                 a1,b1,c;32 int a[maxn];33 int n,m;34 int cnt[maxn];35 void update(int x,int f) {36 if(f) cnt[a[x]]++;37 else cnt[a[x]]--;38 if(cnt[a[x]]) a1[a[x]]=1,b1[maxn-5-a[x]]=1;39 else a1[a[x]]=0,b1[maxn-5-a[x]]=0;40 }41 void work() {42 int l=1,r=0;43 for(int i=1;i<=m;i++) {44 for(;r
                
                 q[i].y;r--) update(r,0);46 for(;l
                 
                  q[i].x;l--) update(l-1,1);48 if(q[i].t==1) {49 c=(a1>>q[i].ask)&a1;50 q[i].ans=c.any();51 }52 else if(q[i].t==2) {53 c=(b1>>abs(maxn-5-q[i].ask))&a1;54 q[i].ans=c.any();55 }56 else {57 int tmp=sqrt(q[i].ask);58 for(int j=1;j<=tmp;j++) {59 if(q[i].ask%j==0) {60 if(cnt[j]&&cnt[q[i].ask/j]) {q[i].ans=1;break;}61 }62 }63 }64 }65 }66 67 int main() {68 n=read(),m=read();69 size=sqrt(n);70 for(int i=1;i<=n;i++) belong[i]=i/size;71 for(int i=1;i<=n;i++) a[i]=read();72 for(int i=1;i<=m;i++) q[i].t=read(),q[i].x=read(),q[i].y=read(),q[i].ask=read(),q[i].id=i;73 sort(q+1,q+m+1,cmp1);74 work();75 sort(q+1,q+m+1,cmp2);76 for(int i=1;i<=m;i++) if(q[i].ans)printf("yuno\n");else printf("yumi\n"); 77 }78