题目链接  BZOJ 4810

首先对询问离线, 莫队算法处理。

首先我们可以用bitset维护处当前区间中是否存在某个数。

对于询问1, 我们可以用 ((f >> q[i].x) & f).any()来回答当前的询问。

对于询问2, 我们用((g >> (S - q[i].x)) & f).any()回答当前询问。

其中g是f的反过来(g[i] = f[S - i])

对于询问3, 我们直接枚举x的因子即可(因为x <= 1e5)

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 1e5 + 10;
const int S = 1e5; int n, m, l, r, BS;
int belong[N], b[N], cnt[N], ans[N];
bitset <N> f, g; struct node{
int op, l, r, x, id;
friend bool operator < (const node &a, const node &b){
return belong[a.l] == belong[b.l] ? belong[a.r] < belong[b.r] : belong[a.l] < belong[b.l];
}
} q[N]; int main(){ scanf("%d%d", &n, &m); BS = (int)sqrt(n + 0.5); rep(i, 1, n) scanf("%d", b + i);
rep(i, 1, m){
int x, y, z, w;
scanf("%d%d%d%d", &x, &y, &z, &w);
q[i] = (node){x, y, z, w, i};
} rep(i, 1, n) belong[i] = (i - 1) / BS + 1;
sort(q + 1, q + m + 1); l = 0, r = 0;
rep(i, 1, m){
while (l > q[i].l){
--l;
++cnt[b[l]];
f[b[l]] = 1;
g[S - b[l]] = 1;
} while (r < q[i].r){
++r;
++cnt[b[r]];
f[b[r]] = 1;
g[S - b[r]] = 1;
} while (l < q[i].l){
--cnt[b[l]];
if (!cnt[b[l]]){
f[b[l]] = 0;
g[S - b[l]] = 0;
}
++l;
} while (r > q[i].r){
--cnt[b[r]];
if (!cnt[b[r]]){
f[b[r]] = 0;
g[S - b[r]] = 0;
}
--r;
} if (q[i].op == 1) ans[q[i].id] = ((f >> q[i].x) & f).any();
if (q[i].op == 2) ans[q[i].id] = ((g >> (S - q[i].x)) & f).any();
if (q[i].op == 3){
if (q[i].x == 0 && f[0]) ans[q[i].id] = 1;
else
for (int j = 1; j * j <= q[i].x; ++j) if (q[i].x % j == 0)
if (f[j] && f[q[i].x / j]){
ans[q[i].id] = 1;
break;
}
} } rep(i, 1, m) puts(ans[i] ? "yuno" : "yumi");
return 0;
}

最新文章

  1. pyMysql
  2. iOS的触摸事件的用法以及和手势识别器的区别
  3. 启动Tomcat服务器报错: Several ports (8005, 8080, 8009) required
  4. thumbnailator图片处理
  5. PHP抓取采集类snoopy介绍
  6. spark下统计单词频次
  7. webrtc学习——mediaStream和MediaStreamTrack
  8. 修改EF的默认约定模型的方式
  9. 获取合并单元格中值的一个方法POI
  10. hdu2377Bus Pass(构建更复杂的图+spfa)
  11. 本人第一个android游戏《新连连看》上架
  12. javascript核心概念之——数组
  13. Java 多线程(一) 基础知识与概念
  14. Java多线程同步问题:一个小Demo完全搞懂
  15. C语言第三次作业---单层循环结构
  16. Pytorch加载模型推荐的方法
  17. ios开发之--NSNumber的使用
  18. table布局 防止table变形 td固定宽度
  19. 说说FATFS文件系统(转)
  20. SVN 定时 更新代码 Demo

热门文章

  1. 【数论 dp】2048
  2. (55)zabbix模板嵌套
  3. Mac单机模式安装启动Kafka
  4. (原)剑指offer之位运算
  5. Lex与Yacc学习(九)之Yacc语法
  6. BFS:UVa220 ACM/ICPC 1992-Othello(黑白棋)
  7. JavaScript正则表达式-RegExp对象
  8. JQuery基本事件函数
  9. python基础学习笔记——开发规范
  10. iOS学习笔记11-多线程入门