[莫隊 bitset] BZOJ 4810 [Ynoi2017]由乃的玉米田

本來還以為有什麼高超的卷積技巧

就是莫隊 + - 直接位移然後&下

至于乘 枚舉所有因數吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;

inline char nc(){
  static char buf[],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-;
  for (x=;c>='0' && c<='9';x=x*+c-'0',c=nc()); x*=b;
}

const int N=;
int pos[N];

struct event{
  int f,l,r,x,idx;
  bool operator < (const event & B) const{
    return pos[l]==pos[B.l]?r<B.r:pos[l]<pos[B.l];
  }
}ev[N];
int ans[N];

int n,m,a[N];
bitset<100001> f,g;
int cnt[N];

inline void add(int x){
  if (cnt[x]==) f[x]=,g[-x]=; cnt[x]++; 
}
inline void del(int x){
  cnt[x]--; if (cnt[x]==) f[x]=,g[-x]=;
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n); read(m); for (int i=;i<=n;i++) read(a[i]);
  for (int i=;i<=m;i++) read(ev[i].f),read(ev[i].l),read(ev[i].r),read(ev[i].x),ev[i].idx=i;
  int B=sqrt(n); for (int i=;i<=n;i++) pos[i]=(i-)/B+;
  sort(ev+,ev+m+);
  int l=,r=;
  for (int i=;i<=m;i++){
    while (r<ev[i].r) add(a[++r]);
    while (r>ev[i].r) del(a[r--]);
    while (l>ev[i].l) add(a[--l]);
    while (l<ev[i].l) del(a[l++]);
    if (ev[i].f==)
      ans[ev[i].idx]=((f>>ev[i].x)&f).any();
    else if (ev[i].f==)
      ans[ev[i].idx]=((g>>(-ev[i].x))&f).any();
    else{
      if (ev[i].x==) { ans[ev[i].idx]=f[]; continue; }
      for (int j=;j*j<=ev[i].x;j++)
    if (ev[i].x%j==)
      if (f[j] && f[ev[i].x/j]){
        ans[ev[i].idx]=; break;
      }
    }
  }
  for (int i=;i<=m;i++)
    printf("%s\n",ans[i]?"yuno":"yumi");
  return ;
}