UOJ Logo

NOI.AC

2S 256MB
Statistics

【题目描述】

给定一串n个珠子,其中每一个珠子的颜色为a[i],总共有k类颜色珠子标号从1到k。

初始给定一个参数T。询问再给定m个区间l[i]到r[i],每次询问这个区间有多少颜色的珠子出现了恰好T次。

【输入格式】

第一行四个整数n,m,k,T(1<=n,m,k,T<=5*10^5)。

第二行n个整数,第i个整数为a[i],表示对应珠子的颜色(1<=a[i]<=k)。

接下来m行,每行两个整数l[i]和r[i],表示询问的区间(1<=l[i]<=r[i]<=n)。

【输出格式】

输出m行,每行一个整数,第i行表示第i次询问的答案。

【样例输入】

10 5 5 1
1 5 3 4 2 4 1 2 3 5 
1 10
3 6 
2 8
5 7
6 10

【样例输出】

0
2
3
3
5

【数据范围】

对于30%的数据 n,m,k<=2000,T<=n.

对于另外40%的数据 T=1,1<=n,m,k<=5*10^5.

对于所有数据,1<=n,m,k,T<=5*10^5,1<=a[i]<=k,1<=l[i]<=r[i]<=n.

注意:本题输入量较大,请使用较为快速的读入方式。