洛谷 P3674 小清新人渣的本愿

想看题目的戳我。

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

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

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

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

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

加法同理。

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

时间复杂度显然是：$O($能过$)$

code:

#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;

}

bitset大法好！

巴特西

洛谷 P3674 小清新人渣的本愿

最新文章

热门文章