文档章节

洛谷 P3674 小清新人渣的本愿

o
 osc_z1hvg4cu
发布于 2018/04/24 21:34
字数 444
阅读 0
收藏 0
c++

精选30+云产品,助力企业轻松上云!>>>

<font size="4">

想看题目的我。

我刚开始觉得这道题目好难。

直到我从Awson大佬那儿了解到有一个叫做bitset的STL,这道题目就很容易被解开了。

想知道这个神奇的bitset的我。

这个题目一看就感觉是莫队,其实是别人告诉我的,分块不太好弄。

减法:$$a-b=x => a=x+b$$就是在权值数组上右移x位。

加法同理。

至于乘法,直接暴力找因子,反正是$\sqrt{n}$复杂度。

时间复杂度显然是:$O($能过$)$ </font>

<hr> <font size="4">code:</font>

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
struct ask {
	int opt,l,r,x,ans,id,ord;
}q[N];
bitset <N> S1,S2;
int n,m,a[N],L=1,R,len,cnt[N];

bool cmp1(ask s,ask t)
{
	return s.id==t.id?s.r<t.r:s.id<t.id;
}

bool cmp2(ask s,ask t)
{
	return s.ord<t.ord;
}

void del(int i)
{
	if (!--cnt[i]) S1[i]=S2[N-i]=0;
}

void ins(int i)
{
	if (!cnt[i]++) S1[i]=S2[N-i]=1;
}

void Mo(int i)
{
	while (L<q[i].l) del(a[L++]);
	while (L>q[i].l) ins(a[--L]);
	while (R<q[i].r) ins(a[++R]);
	while (R>q[i].r) del(a[R--]);
	if (q[i].opt==1) q[i].ans=(S1>>q[i].x&S1).any();
	if (q[i].opt==2) q[i].ans=(S2>>(N-q[i].x)&S1).any();
	if (q[i].opt==3) {
		for (int j=1;j*j<=q[i].x;j++)
		if (q[i].x%j==0&&S1[j]&&S1[q[i].x/j]) {
			q[i].ans=1;break;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	len=sqrt(n);
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=m;i++) {
		cin>>q[i].opt>>q[i].l>>q[i].r>>q[i].x;
		q[i].id=q[i].l/len;q[i].ord=i;
	}
	sort(q+1,q+1+m,cmp1);
	for (int i=1;i<=m;i++) Mo(i);
	sort(q+1,q+1+m,cmp2);
	for (int i=1;i<=m;i++)
	q[i].ans?puts("hana"):puts("bi");
	return 0;
}

<font size="4">bitset大法好!</font>

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

asp.net core之NLog

NuGet添加 NLog.Web.AspNetCore。 <PackageReference Include="Microsoft.AspNetCore.App" /> 添加配置文件 新建一个文件nlog.config(建议全部小写,linux系统中要注意), 并右键点击其属性......

一介草民Coder
57分钟前
23
0
.NET中的struct和class有什么区别? - What's the difference between struct and class in .NET?

问题: .NET中的struct和class有什么区别? 解决方案: 参考一: https://stackoom.com/question/3OT/NET中的struct和class有什么区别 参考二: https://oldbug.net/q/3OT/What-s-the-differ...

富含淀粉
今天
23
0
android:layout_weight是什么意思? - What does android:layout_weight mean?

问题: I don't understand how to use this attribute. 我不明白如何使用这个属性。 Can anyone tell me more about it? 谁能告诉我更多关于它的事情? 解决方案: 参考一: https://stacko...

javail
今天
17
0
CSS背景不透明度[重复] - CSS Background Opacity [duplicate]

问题: This question already has an answer here: 这个问题已经在这里有了答案: How do I give text or an image a transparent background using CSS? 如何使用CSS为文本或图像提供透明背...

fyin1314
今天
31
0
node http 获取gb2312网页如何转为utf8

最初,我想当然认为是下述做法,但被证明是错误的 const http = require('http'), iconv = require('iconv-lite');const url = 'http://xxx';http.get(url, function(res) { var bo......

高延
今天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部