题目概述

给出一个序列 $\{a_n\}$ 和 $m$ 次询问，每次询问 $[L,R]$ 中是否有两个数相加为 $x$ 或两个数相减为 $x$ 或两个数相乘为 $x$ 。

解题报告

看我都死了3个礼拜了，这其实是2个礼拜之前水的题。emm……乱搞大法，首先先莫队把每个区间中的数拿出来，然后记两个bitset就可以瞎搞了（一个是 $x$ 有没有出现，另一个是 $10^5-x$ 有没有出现），至于乘法显然直接枚举就行了。

示例程序

#include<cmath>
#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int maxn=100000,maxm=100000,maxa=100000;

int n,S,m,a[maxn+5],ha[maxa+5];bitset<maxa*2+5> A,B;bool ans[maxm+5];
struct data {int tp,X,Y,x,ID;} q[maxm+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline bool cmp(const data &a,const data &b) {return a.X/S<b.X/S||(a.X/S==b.X/S&&(a.X/S&1?a.Y<b.Y:a.Y>b.Y));}
inline void Insert(int x) {if (!ha[a[x]]++) A[a[x]]=1,B[maxa-a[x]]=1;}
inline void Delete(int x) {if (!--ha[a[x]]) A[a[x]]=0,B[maxa-a[x]]=0;}
int main(){
    readi(n);S=sqrt(n);readi(m);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1;i<=m;i++) readi(q[i].tp),readi(q[i].X),readi(q[i].Y),readi(q[i].x),q[i].ID=i;sort(q+1,q+1+m,cmp);
    for (int i=1,L=1,R=0,x=q[i].x;i<=m;i++,x=q[i].x){
        while (L>q[i].X) Insert(--L);while (L<q[i].X) Delete(L++);
        while (R<q[i].Y) Insert(++R);while (R>q[i].Y) Delete(R--);
        if (q[i].tp==1) ans[q[i].ID]=(A&(A<<x)).any();
        if (q[i].tp==2) ans[q[i].ID]=(A&(B>>(maxa-x))).any();
        if (q[i].tp==3) for (int j=1;j*j<=x;j++) if (!(x%j)&&ha[j]&&ha[x/j]) {ans[q[i].ID]=true;break;}
    }for (int i=1;i<=m;i++) puts(ans[i]?"yuno":"yumi");return 0;
}