Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

04/5
20:53
STL 莫队算法

[bzoj 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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

opt=1或2的时候莫队维护bitset opt=3的时候直接做

 

[bzoj 4810] [Ynoi2017]由乃的玉米田