多组询问不强制在线,那么考虑莫队。bitset维护当前区间出现了哪些数,数组记录每个数的出现次数以维护bitset。对于乘法,显然应有一个根号范围内的因子,暴力枚举即可。对于减法,a[i]-a[j]=x移项得a[i]-x=a[j],可以让bitset大力右移取and。对于加法,a[i]+a[j]=x移项得a[i]=x-a[j],维护一个翻转的bitset大力右移取and。
#include#include #include #include #include #include #include using namespace std;#define ll long long#define N 100010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}bitset f,g;int n,m,a[N],cnt[N];bool flag[N];struct data{ int op,l,r,x,k,i; bool operator <(const data&a) const { return k a.r:r q[i].r) if ((--cnt[a[r--]])==0) f[a[r+1]]=0,g[100000-a[r+1]]=0; while (l>q[i].l) if ((cnt[a[--l]]++)==0) f[a[l]]=1,g[100000-a[l]]=1; while (l >q[i].x)).count(); else flag[q[i].i]=(f&(g>>100000-q[i].x)).count(); } for (int i=1;i<=m;i++) if (flag[i]) printf("yuno\n"); else printf("yumi\n"); return 0;}