小P的太空旅行

时间限制: 1 Sec  内存限制: 128 MB

提交: 41  解决: 17

[] [] [] [命题人:]

题目描述

今年是8102年，小P去M870星球旅行了。M870星球景色优美，食物非常美味，所以全宇宙的人都爱去M870星球旅行。

这些来旅行的游客可以看作一排，来自不同星球的旅客的识别码是不同的，识别码是由1到k的，不同识别码表示不同星球的旅客。

小P想要知道，在一个区间里有多少种出现次数恰好为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 11 5 3 4 2 4 1 2 3 5 1 103 6 2 85 76 10

样例输出

02335

 

提示

对于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.

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

Solution：注意一下输入输出的优化就好了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn=5e5+10;template 
           
            inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); }}template 
            
             inline void print_d(T x){ if(x > 9)print_d(x / 10); putchar(x % 10 + '0');}struct node{ int l,r,id,pos; bool operator<(const node& x){ if(pos==x.pos)return r
             
              l){ vis[p[l]]--; if(vis[p[l]]==t)cur++; else if(vis[p[l]]!=t&&vis[p[l]]+1==t)cur--; l++; } while(cr
              
               r){ vis[p[++r]]++; if(vis[p[r]]==t)cur++; else if(vis[p[r]]!=t&&vis[p[r]]-1==t)cur--; } ans[q[i].id]=cur; } REP(i,1,m){ print_d(ans[i]); puts(""); } return 0;}