T366188 提瓦特逸事:璃月篇

>“此世群魔诸神并起，我虽无意逐鹿，却知苍生苦楚。 >只愿荡涤四方，护得浮生一隅。” > ————钟离 看着这些话，七七暗暗想，她也要成为如此伟大的人。 于是，她打通了“夜叉热线”，虽然被称为热线，但电话那头人的语气，却总显得些许冰冷，比如这次—— “要突破？好。”顷刻间，一缕黑烟，伴随一位少年的身影出现，几乎同时，又消失不见，只听到满地经验书掉落的声音。 经验书总数为 $n$ ，每本经验书都有各自的等级 $Lev\ (Lev\in\mathbb{N})$。为了便于处理（~~急着去不卜庐上班~~）七七暂时将它们~~随意~~摆成了一排，并从左到右依次编了序号。为了避免升级等级时经验溢出，她想知道一些信息——

七七想要知道哪些区间 $[L,R]$ 内有最少种类的经验书， ~~“绝对...绝对不是因为我只会数到...数到七”~~， 于是，她找到了刚学会树状数组的你来解决这一个问题。 同时，她怕太麻烦你， ~~“绝对...绝对不是想找最少...最少的种类”~~， 只是询问了 $m$ 个**给定区间 $[L,R]$ 内有多少种不同的经验书**，~~然后自己偷偷求最小值~~

第一行为一个整数 $n$ 和 $m$，意义如题目背景和描述所述。 第二行为 $n$ 个整数，第 $i$ 个整数表示经验书的等级为 $Lev_i$ 接下来 $m$ 行，每行两个数 $l$ 和 $r$，代表此次询问的区间

输出共 $m$ 行，第 $i$ 行表示对于第 $i$ 次询问，对应区间内经验书的种类数

**题解已完成**，[传送门](https://www.luogu.com.cn/blog/OtakusHouse/Teyvat-Liyue-Solution) 对于 $20\%$ 的数据，$1 \le n \le m \le 5000$ 对于 $40\%$ 的数据，$1 \le n \le m \le 10^5$ 对于 $60\%$ 的数据，$1 \le n \le m \le 5\times10^5$ 对于 $100\%$ 的数据，$1 \le n \le m \le Lev_i\le 10^6$ 除 $data8.in$ 和 $data1.in$ 外，保证数据由Zar随机生成 由于七七说话有点结巴，你最好使用快速读入:) ------------ “旅行者，我给你划掉...划掉的那些字，你删没删?” “删没删的话...如删嘛” 附：出现过的人物立绘    另外:本题底层知识点均借鉴了官方题库，可以作为树状数组加强练习食用 本人第一次出题，含有娱乐(夹带私货)性质，有不妥之处请见谅