1.算法

尺取+树状数组(nlogn)

2.实现

对于每个i来说,维护一个[l,r].然后对于每个i维护一个区间L[i],R[i]表示这个区间最大数量为k的可行区间.这里可以用个尺取就行.求出区间了之后呢,因为离线,我们可以考虑将所有区间进行排序.然后对于每个区间来说,我们可以枚举移动的点,也就是i,然后更新这个区间的答案,因为是排序完了所以必然是互不影响的,我只要控制指针移动即可得到答案.

3.代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+50;
struct vv{
    int l,r,id;ll ans;
}vnt[N];

bool cmp1(vv a,vv b)
{
     if(a.l==b.l)   return a.r<b.r;
     else           return a.l<b.l;
}//按左端点优先,其次右端点排列.

bool cmp2(vv a,vv b)
{
    return a.id<b.id;
}//输出答案

int n,cntl[N],cntr[N],L[N],R[N],a[N],q,k;
ll c1[N],c2[N];

ll lowbit(ll x)   {  return x&(-x); }

void add(ll pos,ll val)
{
    ll x=pos;
    while(pos<=n)
    {
        c1[pos]+=val;
        c2[pos]+=(x-1)*val;
        pos+=lowbit(pos);
    }
}

ll query(ll pos)
{
    ll res=0;ll x=pos;
    while(pos)
    {
        res+=x*c1[pos]-c2[pos];
        pos-=lowbit(pos);
    }return res;
}

void init()//预处理出L,R数组.
{
    //cout<<k<<endl;
    int l=1,r=1;//设立两个指针.
    for(int i=1;i<=n;i++)
    {
        //处理l
        while(l<=n&&cntl[a[l]]+1<k) {  cntl[a[l]]++,l++; }
        //处理r
        while(r<=n&&cntr[a[r]]+1<=k) {  cntr[a[r]]++,r++; }
        r--,cntr[a[r]]--,L[i]=l,R[i]=r;
        cntl[a[i]]--,cntr[a[i]]--;
    }
}

void BUG()
{
    for(int i=1;i<=n;i++)   cout<<L[i]<<' '<<R[i]<<endl;
    /*
    5 3 2           n q k
    1 2 2 1 2

    5 5
    5 4
    6 5
    6 5
    6 4
    */
}

int main()
{
    scanf("%d%d%d",&n,&q,&k);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=1;i<=q;i++)
        scanf("%d%d",&vnt[i].l,&vnt[i].r),vnt[i].id=i;
    sort(vnt+1,vnt+1+q,cmp1);
    init();
    //BUG();
    int l=1,r=0;
    for(int pos=1;pos<=q;pos++)//枚举区间.
    {
        //(L[i],R[i])   || (vnt[i].l,vnt[i].r)
        while(l<vnt[pos].l)   add(L[l],-1),add(R[l]+1,1),l++;
        while(r<vnt[pos].r)   add(L[++r],1),add(R[r]+1,-1);
        vnt[pos].ans=query(vnt[pos].r)-query(vnt[pos].l-1);
    }
    sort(vnt+1,vnt+1+q,cmp2);
    for(int i=1;i<=q;i++)   printf("%lld\n",vnt[i].ans);
    return 0;
}
/*
    模拟你都不会好意思打算法竞赛?
*/