BZOJ 4810 [Ynoi2017]由乃的玉米田 ——Bitset 莫队算法
2024-10-21 09:52:10
加法和减法的操作都能想到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");
}
最新文章
- windows命令——explorer
- SQL 2012 镜像 图解(解决1418)
- ps 图片提取线稿方法2种 转
- Win7下部署 .NET MVC网站 之 HTTP错误 403.14-Forbidden 解决方法
- 消息对话框(MessageBox)用法介绍
- C++拷贝构造函数总结
- Canvas绘制一个大鱼喂小鱼的游戏
- c++面试遇到问题
- 解决WebView加载本地文件乱码
- Yii2设计模式——简单工厂模式
- FastAdmin笔记~
- fcn+caffe+voc2012实验记录
- MyBatis中Mapper的返回值类型
- Android 5.0 API
- Android应用一般上架流程
- Mysql进阶-day2
- System.IO命名空间下常用的类
- WPF比较两个随机数大小写,利用MVVM思想实现
- 51nod 1344 走格子【贪心/前缀和】
- 使用Visual Studio进行单元测试-Part4
热门文章
- Ubuntu16.04 + cuda8.0 + GTX1080安装教程
- c语言中的赋值
- ZOJ 3466 The Hive II (插头DP,变形)
- Git服务器和Git权限管理应用GITLAB安装方法
- websphere7.0异常:SRVE0255E: 尚未定义要处理 /wcm 的 Web 组/虚拟主机
- null 理解
- 在tomcat中配置连接池
- Bootstrap响应式布局(1)
- 关于windows server 2003 IE 不能访问 https问题
- java在线聊天项目0.5版 解决客户端向服务器端发送信息时只能发送一次问题 OutputStreamWriter DataOutputStream socket.getOutputStream()