加法和减法的操作都能想到Bitset。

然后发现乘法比较难办,反正复杂度已经是$O(n\log{n})$了

枚举因数也不能更差了,直接枚举就好了。

#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define maxn 100005 bitset <100010> a,b; int T,tot,L[maxn],R[maxn],n,m,c[maxn],bel[maxn]; struct Query{
int l,r,opt,x,id;
bool operator < (const Query & a)const {
return bel[l]==bel[a.l]?r<a.r:bel[l]<bel[a.l];
}
}q[maxn]; void init()
{
T=sqrt(n);
for(int i=1;i<=n;i+=T)L[++tot]=i,R[tot]=i+T-1;
R[tot]=n;
F(i,1,tot) F(j,L[i],R[i]) bel[j]=i;
} int cnt[maxn],ans[maxn]; void add(int x)
{cnt[x]++;if(cnt[x]==1)a[x]=1,b[maxn-x]=1;} void dec(int x)
{cnt[x]--;if (!cnt[x]) a[x]=0,b[maxn-x]=0;} bool Cha(int x)
{
if (((a>>x)&a).count()) return true;
return false;
} bool He(int x)
{
if (((b>>(maxn-x))&a).count()) return true;
return false;
} bool Mul(int x)
{
int lim=sqrt(x+1);
F(i,1,lim)if(!(x%i))if (a[i]&&a[x/i]) return true;
return false;
} int main()
{
scanf("%d%d",&n,&m);init();
F(i,1,n) scanf("%d",&c[i]);
F(i,1,m)
{
scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x);
q[i].id=i;
}
sort(q+1,q+m+1);
int l=1,r=0;
F(i,1,m)
{
while (r<=q[i].r) add(c[++r]);
while (r>q[i].r) dec(c[r--]);
while (l<=q[i].l) dec(c[l++]);
while (l>q[i].l) add(c[--l]);
switch(q[i].opt)
{
case 1: if (Cha(q[i].x)) ans[q[i].id]=1; break;
case 2: if (He(q[i].x)) ans[q[i].id]=1; break;
case 3: if (Mul(q[i].x)) ans[q[i].id]=1; break;
}
}
F(i,1,m)
if (ans[i]) printf("yuno\n");
else printf("yumi\n");
}

  

最新文章

  1. windows命令——explorer
  2. SQL 2012 镜像 图解(解决1418)
  3. ps 图片提取线稿方法2种 转
  4. Win7下部署 .NET MVC网站 之 HTTP错误 403.14-Forbidden 解决方法
  5. 消息对话框(MessageBox)用法介绍
  6. C++拷贝构造函数总结
  7. Canvas绘制一个大鱼喂小鱼的游戏
  8. c++面试遇到问题
  9. 解决WebView加载本地文件乱码
  10. Yii2设计模式——简单工厂模式
  11. FastAdmin笔记~
  12. fcn+caffe+voc2012实验记录
  13. MyBatis中Mapper的返回值类型
  14. Android 5.0 API
  15. Android应用一般上架流程
  16. Mysql进阶-day2
  17. System.IO命名空间下常用的类
  18. WPF比较两个随机数大小写,利用MVVM思想实现
  19. 51nod 1344 走格子【贪心/前缀和】
  20. 使用Visual Studio进行单元测试-Part4

热门文章

  1. Ubuntu16.04 + cuda8.0 + GTX1080安装教程
  2. c语言中的赋值
  3. ZOJ 3466 The Hive II (插头DP,变形)
  4. Git服务器和Git权限管理应用GITLAB安装方法
  5. websphere7.0异常:SRVE0255E: 尚未定义要处理 /wcm 的 Web 组/虚拟主机
  6. null 理解
  7. 在tomcat中配置连接池
  8. Bootstrap响应式布局(1)
  9. 关于windows server 2003 IE 不能访问 https问题
  10. java在线聊天项目0.5版 解决客户端向服务器端发送信息时只能发送一次问题 OutputStreamWriter DataOutputStream socket.getOutputStream()