D.离别

https://ac.nowcoder.com/acm/contest/9033/D

存个代码，对于询问区间，求其子区间满足 不同数的种类恰好是K。(假题意,假代码，还未验证正确性

#include<bits/stdc++.h>


using namespace std;
const int maxn=1e6+10;

typedef long long ll;
int re[maxn],le[maxn],a[maxn],id[maxn];
ll sum[maxn];
int vis[maxn],block,res=0;
ll ans[maxn];

int n,m,k;

struct node
{
    int l,r,pr;
    int id;
    friend bool operator < ( node a, node b )// 分块排序
    {
        if( a.l/block==b.l/block ) return a.r<b.r;  
        return a.l/block<b.l/block;
    }
}que[maxn];

map<int,int> mp;

#define lowbit(x) x&(-x)
ll sum1[maxn],sum2[maxn];
int cnt=5e5;
void add( ll a[],int x,int C ) { while( x<=cnt ) a[x]+=C,x+=lowbit(x); }
ll query( ll a[],int x ) { ll ans=0; while( x ) ans+=a[x],x-=lowbit(x); return ans; }


void add( int x )
{
    if( le[x]==1e6 ) return;
    add(sum1,le[x],-le[x]);
    add(sum1,re[x],re[x]+1);
    add(sum2,le[x],1);
    add(sum2,re[x],-1); 
}

void del( int x )
{
    add(sum1,le[x],le[x]);
    add(sum1,re[x],-re[x]-1);
    add(sum2,le[x],-1);
    add(sum2,re[x],1);
}


int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    block=sqrt(n);
    for( int i=1;i<=n;i++ ) scanf("%d",&a[i]),re[i]=le[i]=1e6;


    for( int i=1;i<=m;i++ ) 
    {
        scanf("%d%d",&que[i].l,&que[i].r);
        que[i].id=i;
        que[i].pr=que[i].r;
    }

    k++;
    int lef=1,rig=0;
    while( lef<=n )
    {
        while( rig<=n && mp.size()<k ) 
        {
            rig++;
            if( rig<=n ) mp[a[rig]]++;
        }
    //    cout<<mp.size()<<"\n";
        if( rig>n && mp.size()!=k-1 ) break;
        re[lef]=rig-1;
        mp[a[lef]]--;
        if( mp[a[lef]]==0 ) mp.erase(a[lef]);
        lef++;
    }
    mp.clear();
    k--;
    lef=1,rig=0;
    while( lef<=n )
    {
        while( rig<=n && mp.size()<k ) 
        {
            rig++;
            if( rig<=n ) mp[a[rig]]++;
        }
        if( rig>n ) break;
        le[lef]=rig;
        mp[a[lef]]--;
        if( mp[a[lef]]==0 ) mp.erase(a[lef]);
        lef++;
    }

    /*
    for( int i=1;i<=n;i++ )
    {
        cout<<le[i]<<" "<<re[i]<<"\n";
    }
    */

    for( int i=1;i<=m;i++ )
    {
        int nl=que[i].l,nr=que[i].r;
        int ed=0,mid=0;
        while( nl<=nr )
        {
            int mid=nl+nr>>1;
            if( le[mid]<=que[i].r ) nl=mid+1,ed=mid;
            else nr=mid-1;
        }
        que[i].r=ed;    
    }



    sort(que+1,que+m+1);

/*
    for( int i=1;i<=m;i++ )
    {
        cout<<que[i].l<<" "<<que[i].r<<"\n";

    }
*/

    int l=1,r=0;
    for( int i=1;i<=m;i++ )
    {
        while( l<que[i].l ) del(l),l++;
        while( l>que[i].l ) l--,add(l);
        while( r<que[i].r ) r++,add(r);
        while( r>que[i].r ) del(r),r--;
        int pos=que[i].pr;
    //    cout<<query(sum1,pos)<<" "<<query(sum2,pos)<<"\n";
        ans[que[i].id]=query(sum1,pos)+1ll*query(sum2,pos)*(pos+1); 
    }
    for( int i=1;i<=m;i++ ) printf("%lld\n",ans[i]);


    return 0; 
}