Description
题目描述
这个题是这样的:
给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1,2,3
选出的这两个数可以是同一个位置的数
输入格式
第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作,l,r表示操作的区间,x表示这次操作的x
输出格式
对于每个询问,如果可以,输出hana,否则输出bi
Code
#include <cstdio> #include <cstdlib> #include <algorithm> #include <bitset> #include <cmath> using namespace std; const int N=1e5; bitset <N+10> a,b,c; int n,m,d[N+10],pos[N+10],si,bl,ans[N+10],nl=1,nr,s[N+10]; struct node { int opt,l,r,x,id; bool operator <(const node &o)const { return pos[l]^pos[o.l]?l<o.l:pos[l]&1?r<o.r:r>o.r; } }q[N]; void get(int x,int y) { if(y==1) { if(s[x]++==0) a[x]=1,b[N-x]=1; } else { if(--s[x]==0) a[x]=0,b[N-x]=0; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); si=sqrt(n); for(int i=1;i<=n;i++) pos[i]=(i-1)/si+1; for(int i=0;i<m;i++) scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x),q[i].id=i; sort(q,q+m); for(int i=0;i<m;i++) { while(nl<q[i].l) get(d[nl++],-1); while(nl>q[i].l) get(d[--nl],1); while(nr<q[i].r) get(d[++nr],1); while(nr>q[i].r) get(d[nr--],-1); if(q[i].opt==1) { c=a&(a<<q[i].x); if(c.any()) ans[q[i].id]=1; } else if(q[i].opt==2) { c=a&(b>>(N-q[i].x)); if(c.any()) ans[q[i].id]=1; } else if(q[i].opt==3) { int sq=sqrt(q[i].x); for(int j=1;j<=sq;j++) if(q[i].x%j==0 && s[j] && s[q[i].x/j]) { ans[q[i].id]=1; break; } } } for(int i=0;i<m;i++) if(ans[i]) puts("hana"); else puts("bi"); return 0; }