题号：NC214006
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
此次离别，至少也要一年半吧。
最后,树剖准备出一套题,作为和OI圈的告别赛.
树剖现在有n个题,每个题有一个类型ai,还有一个参数k.
因为一些原因,树剖给了自己q个询问,每次询问l,r.
对于每个询问,树剖决定在区间中选一个子区间
,作为比赛赛题.
但是树剖不希望同一类型的题太多或太少,所以她要求比赛赛题里出现次数最多的类型恰好出现k次.
现在对于每个询问,您需要回答,树剖有多少种子区间选择方案
树剖现在有n个题,每个题有一个类型ai,还有一个参数k.
因为一些原因,树剖给了自己q个询问,每次询问l,r.
对于每个询问,树剖决定在区间中选一个子区间
但是树剖不希望同一类型的题太多或太少,所以她要求比赛赛题里出现次数最多的类型恰好出现k次.
现在对于每个询问,您需要回答,树剖有多少种子区间选择方案
输入描述:
第一行,三个正整数n,q,k.
第二行n个正整数,ai
后面q行,每行2个正整数,l,r,表示一次询问.
输出描述:
q行,每行一个数,第i个表示第i次询问的答案