#2258. [AHOI2013]作业

    ID: 2258 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>其他莫队数据结构树状数组块状链表分块块状数组

[AHOI2013]作业

题目描述

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

这时小 A 碰见了一道非常恶心的数学题,给定了一个长度为 nn 的数列和若干个询问,每个询问是关于数列的区间表示数列的第 ll 个数到第 rr 个数),首先你要统计该区间内大于等于 aa,小于等于 bb 的数的个数,其次是所有大于等于 aa,小于等于 bb 的,且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望,只能向大神您求救,请您帮帮他吧。

输入格式

第一行两个整数 n,mn,m

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

接下来 mm 行,每行四个整数 l,r,a,bl,r,a,b,具体含义参见题意。

输出格式

输出 mm 行,分别对应每个询问,输出两个数,分别为在 llrr 这段区间中大小在 [a,b][a,b] 中的数的个数,以及大于等于 aa,小于等于 bb 的,且在该区间中出现过的数值的个数(具体可以参考样例)。

样例

1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
2 2
1 1
3 2
2 1

数据范围

N100000,M100000N\leq 100000,M\leq 100000,读入的数字均为 [1,105][1,10^5] 内的正整数。