【树状数组】小P的太空旅行

60 阅读 0 评论 40 点赞

我是靠谱客的博主会撒娇耳机，最近开发中收集的这篇文章主要介绍【树状数组】小P的太空旅行，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

【题意】：

给你n,m,k,T,分别是，n个数，m个询问区间[L,R]，k种数字，请问在所问的区间内有多少种数恰好为T

首先有一个暴力的做法：其实不是正解，就是莫队算法，维护一个种类数即可。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],vis[N],ans[N];
typedef struct Node{
    int No,L,R;
}Node;
Node Q[N];
int n,m,k,T,block,cnt;
void Add(int x){
    vis[x]++;
    if(vis[x]==k){
        cnt++;
    }else if(vis[x]==k+1){
        cnt--;
    }
}
void Del(int x){
    vis[x]--;
    if(vis[x]==k){
        cnt++;
    }else if(vis[x]==k-1){
        cnt--;
    }
}
int cmp(Node a,Node b){
    return a.L/block==b.L/block?a.R<b.R:a.L/block<b.L/block;
}
int main()
{
    scanf("%d%d%d%d",&n,&T,&m,&k);//输入出现一些问题，
    //这里是n个数，m个种类，选择K个，T次询问
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<T;i++){
        scanf("%d%d",&Q[i].L,&Q[i].R);
        Q[i].No=i;
    }
    block=(int)pow(n,0.5);
    sort(Q,Q+T,cmp);
    int L=0,R=0;
    for(int i=0;i<T;i++){
        while(R<Q[i].R) Add(a[++R]);
        while(R>Q[i].R) Del(a[R--]);
        while(L<Q[i].L) Del(a[L++]);
        while(L>Q[i].L) Add(a[--L]);
        ans[Q[i].No]=cnt;
    }
    for(int i=0;i<T;i++){
        printf("%dn",ans[i]);
    }

}

正解是：

维护一个树状数组，树状数组是从后往前维护的。

表示的是在getsum( i ) 即以i为前缀和即[1,i]里的恰好为T的种类数。

但是需要维护右边界。

胜营兄的题解

1、因为我们需要维护右边界，所以我们需要把询问的区间排序一下。

2、我们按照种类从小到大：用数组now记录，第K种的最后倒数第T个出现的位置，用pre数组记录每一次种类对应下标的前一个，所以我们可以进行处理，即update( now[k], 1),update ( pre[now[k]] , -1 )

3、排序后，随着右端点的移动，不断维护种类数。

因为随着右端点往左移，区间减少，相对应的种类前T个，进行修改，因为当前位置的种类的个数减去1，所以需要更新维护。

首先我们必须把之前位置撤标，

即：update( now[k], -1),update ( pre[now[k]] , 1 )

然后下一个now[k]随之变化，变成now[k] = pre[now[k]]，

然后重新维护update( now[k], 1),update ( pre[now[k]] , -1 )

后来发现其实这两个端点，有一个是重复了，L1,R1==L2,R2.

update( L1,-1), update(R1,2),update(R2,-1)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,k,T;
int a[N],c[N],pre[N],now[N],ans[N];
int lowbit(int x){
    return x&(-x);
}
void update(int x,int val){
    if(x)
    for( ;x<=n;x+=lowbit(x)){
        c[x]+=val;
    }
}
int getsum(int x){
    int res=0;
    for( ;x>0;x-=lowbit(x)){
        res+=c[x];
    }
    return res;
}
typedef struct Node{
    int L,R,No;
}Node;
bool cmp(Node a,Node b){
    return a.R>b.R;
}
Node Q[N];
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&T);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pre[i]=now[a[i]];
        now[a[i]]=i;
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&Q[i].L,&Q[i].R);
        Q[i].No=i;
    }
    sort(Q,Q+m,cmp);
    for(int i=1;i<=k;i++){
        int x=T-1;
        while(now[i]&&x){
            now[i]=pre[now[i]];
            x--;
        }
        if(now[i]){
            update(now[i],1);
            update(pre[now[i]],-1);
        }
    }
    int R=n;
    for(int i=0;i<m;i++){
        while(Q[i].R<R){
            update(now[a[R]],-1);
            update(pre[now[a[R]]],2);
            update(pre[pre[now[a[R]]]],-1);
            now[a[R]]=pre[now[a[R]]];
            R--;
        }
        ans[Q[i].No]=getsum(Q[i].R)-getsum(Q[i].L-1);
    }
    for(int i=0;i<m;i++){
        printf("%dn",ans[i]);
    }
    return 0;
}