BZOJ 4810 [Ynoi2017]由乃的玉米田 (莫队 + bitset)
2024-10-21 03:53:03
题目链接 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;
}
最新文章
- pyMysql
- iOS的触摸事件的用法以及和手势识别器的区别
- 启动Tomcat服务器报错: Several ports (8005, 8080, 8009) required
- thumbnailator图片处理
- PHP抓取采集类snoopy介绍
- spark下统计单词频次
- webrtc学习——mediaStream和MediaStreamTrack
- 修改EF的默认约定模型的方式
- 获取合并单元格中值的一个方法POI
- hdu2377Bus Pass(构建更复杂的图+spfa)
- 本人第一个android游戏《新连连看》上架
- javascript核心概念之——数组
- Java 多线程(一) 基础知识与概念
- Java多线程同步问题:一个小Demo完全搞懂
- C语言第三次作业---单层循环结构
- Pytorch加载模型推荐的方法
- ios开发之--NSNumber的使用
- table布局 防止table变形 td固定宽度
- 说说FATFS文件系统(转)
- SVN 定时 更新代码 Demo