小清新人渣的本愿

题目描述

这个题是这样的:

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

选出的这两个数可以是同一个位置的数

输入输出格式

输入格式:

第一行两个数n,m

后面一行n个数表示ai

后面m行每行四个数opt l r x

opt表示这个是第几种操作,l,r表示操作的区间,x表示这次操作的x

输出格式:

对于每个询问,如果可以,输出hana,否则输出bi

输入输出样例

输入样例#1: 复制
输出样例#1: 复制
输入样例#2: 复制
输出样例#2: 复制

说明

定义c为每次的x和ai中的最大值,ai >= 0,每次的x>=2

对于10%的数据,n,m,c <= 100

对于另外10%的数据,n,m,c <= 3000

对于另外10%的数据,只有1操作

对于另外10%的数据,只有2操作

对于另外10%的数据,只有3操作

对于100%的数据,n,m,c <= 100000


用bitset维护每个数是否出现过

查询是否有差为x,即为(a & (a << x)).any()

加则维护一个反bitset

乘则枚举约数

总复杂度O(c/64*n^(1/2)*n)

不过比预想的跑得快?


 

发表评论