分析

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

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

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

  • 图例
    图片说明

    代码

    #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;
    }