此次离别，至少也要一年半吧， 最后,树剖准备出一套题,作为和OI圈的告别赛. 树剖现在有n个题,每个题有一个类型ai,还有一个参数k. 因为一些原因,树剖给了自己q个询问,每次询问l,r. 对于每个询问,树剖决定在区间中选一个子区间[l′,r′],l≤l′≤r′≤r[l',r'],lle l'le r' le r[l′,r′],l≤l′≤r′≤r,作为比赛赛题. 但是树剖
此次离别，至少也要一年半吧。 最后,树剖准备出一套题,作为和OI圈的告别赛. 树剖现在有n个题,每个题有一个类型ai,还有一个参数k. 因为一些原因,树剖给了自己q个询问,每次询问l,r. 对于每个询问,树剖决定在区间中选一个子区间[l′,r′],l≤l′≤r′≤r[l',r'],lle l'le r' le r[l′,r′],l≤l′≤r′≤r,作为比赛赛题. 但是树剖不希望同一类型的题太多或太少,所以她要求比赛赛题里出现次数最多的类型恰好出现k次. 现在对于每个询问,您需要回答,树剖有多少种子区间选择方案
（图片来源网络，侵删）
