题目描述

输入

输出

样例输入

3 4

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

提示

N=100000,M=1000000

 

莫队+树状数组：

先考虑每次询问没有权值区间限制的情况，将询问离线排序，用一个数组记录答案，莫队即可。

但现在每次询问有了查询的权值区间，显然一个数组无法记录答案，我们用树状数组来记录答案。

对于第一问直接用树状数组即可，对于第二问先用数组记录每个权值是否出现过再用树状数组维护即可。

莫队时间复杂度是$O(mlog_{n}\sqrt{n})$，查询时间复杂度是$O(mlog_{n})$。

#include
      
       #include
       
      

莫队+分块：

可以发现莫队+树状数组的做法时间复杂度主要在双指针移动时对答案的维护。

我们将树状数组改成分块，那么单次移动指针时间复杂度为$O(1)$，而单次查询的时间复杂度是$O(\sqrt{n})$。

这样莫队的时间复杂度是$O(m\sqrt{n})$，查询的时间复杂度为$O(m\sqrt{n})$。

#include
      
       #include