BZOJ 4810 由乃的玉米田 （莫队+压位）

发表于 |
字数统计: 802字 | 阅读时长 ≈ 4min

4810: [Ynoi2017]由乃的玉米田

Description

由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。
由乃认为玉米田不美，所以她决定出个数据结构题

这个题是这样的：
给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是
否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1
,2,3选出的这两个数可以是同一个位置的数

Input

第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作，l,r表示操作的区间，x表示这次操作的x
定义c为每次的x和ai中的最大值，ai >= 0，每次的x>=2n,m,c <= 100000

Output

对于每个询问，如果可以，输出yuno，否则输出yumi

Sample Input

5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4

Sample Output

yuno
yumi
yuno
yuno
yumi

首先，如果维护了$[l,r]$的权值出现情况，用一个bitset $F$表示数字$i$是否存在
那么对于询问1，就是$F$&$(F<<x)$是否存在1
对询问二，令$G[i]=F[n-i]$，那么就是$G$&$(F<<100000-x)$
对询问三，分解因数暴力判断即可。

关于如何维护$[l,r]$的bitset，用莫队即可。总复杂度$O(n\sqrt{n}+\frac{nm}{32})$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
#define N 100005
using namespace std;
const int T=100000;
bitset<100000>F,G;
int n,m,A[N],cnt[N],id[N],S;
bool Ans[N];
struct node{int l,r,x,ty,id;}K[N];
bool cmp(node a,node b)
{
	if(id[a.l]==id[b.l])return a.r<b.r;
	return id[a.l]<id[b.l];
}
void UD(int k,int ty)
{
	k=A[k];
	if(cnt[k])F[k]=0,G[T-k]=0;
	cnt[k]+=ty;
	if(cnt[k])F[k]=1,G[T-k]=1;
}
bool Gans(int ty,int x)
{
	if(ty==1)
	{
		bitset<100000>tmp=(F<<x)&F;
		return tmp.any();
	}
	if(ty==2)
	{
		bitset<100000>tmp=(F<<T-x)&G;
		return tmp.any();
	}
	if(ty==3)
	{
		for(int i=1;i*i<=x;i++)
		if(x%i==0&&F[i]&&F[x/i])return 1;
		return 0;
	}
}
int main()
{
	int i,j,k,x,y,z,L,R;
	scanf("%d%d",&n,&m);
	S=sqrt(n);
	for(i=j=1;i<=n;i++)scanf("%d",&A[i]),id[i]=i%S?j:j++;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&k,&L,&R,&x);
		K[i]=(node){L,R,x,k,i};
	}
	sort(K+1,K+m+1,cmp);
	L=1;R=0;
	for(i=1;i<=m;i++)
	{
		while(K[i].r<R)UD(R--,-1);
		while(K[i].r>R)UD(++R,1);
		while(K[i].l<L)UD(--L,1);
		while(K[i].l>L)UD(L++,-1);
		Ans[K[i].id]=Gans(K[i].ty,K[i].x);
	}
	for(i=1;i<=m;i++)Ans[i]?puts("yuno"):puts("yumi");
}