#P3236. [Ahoi2013]作业

    ID: 2421 传统题 5000ms 512MiB 尝试: 2292 已通过: 566 难度: 6 上传者: 标签>难度分类提高离线与分治普通莫队数据结构根号分块奇偶块排序CF2100

[Ahoi2013]作业

[AHOI2013] 作业

题目描述

此时己是凌晨两点,刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多,一个小时刚好可以做完。然后是一个小时可以做完的数学作业,接下来是分别都是一个小时可以做完的化学,物理,语文……小 A 压力巨大。

给定一个长度为 nn 的数列。每次询问给出下标区间 [l,r][l,r] 和数值区间 [a,b][a,b],求 ll 至 rr 之间有多少个元素的值落在 [a,b][a,b] 内,以及这些元素有多少种不同的值。

输入格式

第一行包含两个整数 n,mn,m,分别为数列长度和询问次数。

接下来 nn 个不超过 10510^5 的正整数表示数列

接下来 mm 行,每行四个整数 l,r,a,bl,r,a,b,其中 1≤l≤r≤n1\le l\le r\le n,1≤a≤b≤1051\le a\le b\le 10^5。

输出格式

对每次询问输出一行两个整数,依次表示符合条件的元素总数和不同值的个数。

样例 #1

样例输入 #1

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

样例输出 #1

2 2
1 1
3 2
2 1

提示

1≤n≤1051\le n\le 10^5,1≤m≤1061\le m\le 10^6。数列中的元素及询问的数值端点均为 [1,105][1,10^5] 内的整数。