分析

欢迎私聊，感觉说的不太清晰。

• 我们考虑如何保证每个区间的某一个种类个数达到 。这个我们可以考虑离线询问，将 的询问差分成 的答案。那么我们先把一个询问拆分成两个，再来考虑前缀的做法 。我们对于每个数，保留它的前一个和他相同相同的元素。那么枚举的右端点到了 ，那么左端点在 都是可以保证区间恰好 个的。那么这个我们可以考虑使用线段树来维护。

• 如何保证我们枚举的区间是保证它是最大元素。这个可以考虑动态维护两个指针 。 我们每当这两个指针中相同元素到达了 时，就移动到这个元素的 处，这样就保证了这个区间最多出现 个相同元素。

• 图例
  

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define pii pair<int,int>
  #define ll long long
  ll read() {
    ll x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
  }
  const ll N = 3e5 + 1000;
  ll tag[N << 2],sum[N << 2];
  void pushdown(ll x,ll l,ll r) {
    if(tag[x]) {
        ll mid = l + r >> 1;
        tag[x << 1] += tag[x];tag[x << 1 | 1] += tag[x];
        sum[x << 1] += (mid - l + 1) * tag[x];
        sum[x << 1 | 1] += (r - mid) * tag[x];
        tag[x] = 0;
    }
  }
  void update(ll u,ll l,ll r,ll L,ll R,ll vl) {
    if(l > R || r < L) return;
    if(L <= l && r <= R) {tag[u] += vl;sum[u] += (r - l + 1) * vl;return;}
    ll mid = (l + r) >> 1;pushdown(u,l,r);
    update(u << 1,l,mid,L,R,vl);update(u << 1 | 1,mid + 1,r,L,R,vl);
    sum[u] = (sum[u << 1] + sum[u << 1 | 1]); 
  } 
  ll ask(ll u,ll l,ll r,ll L,ll R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum[u]; 
    ll mid = (l + r) >> 1;pushdown(u,l,r);
    return ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R);
  }
  struct Node {ll l,r,type,id;};
  vector<Node> Q[N];
  ll n,m,k,A[N],si[N],ans[N];
  vector<ll> pos[N];
  int main() {
    n = read();m = read();k = read();
    for(ll i = 1;i <= n;i++) A[i] = read();
    for(ll i = 1;i <= m;i++) {
        ll l = read(),r = read();
        Q[r].push_back((Node){l,r,1,i});
    } 
    for(ll i = 1;i <= n;i++) si[i] = pos[A[i]].size(),pos[A[i]].push_back(i);
    for(ll i = 1,l = 0,r = 0;i <= n;i++) {
        if(si[i] >= k - 1) r = max(r,pos[A[i]][si[i] - k + 1]);
        if(si[i] >= k) l = max(l,pos[A[i]][si[i] - k]);
        if(l < r) update(1,1,n,l+1,r,1);
        for(auto x : Q[i]) {
            ans[x.id] += x.type * ask(1,1,n,x.l,x.r); 
        }
    }
    for(ll i = 1;i <= m;i++) printf("%lld\n",ans[i]);
    return 0;
  }