洛谷 P1972 [SDOI2009]HH的项链—

先上一波题目 https://www.luogu.org/problem/P1972

这道题是询问区间内不同数的个数明显不是正常的数据结构能够维护的

首先考虑因为对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的

例如项链：1 3 4 5 1

那么，对于r=5的所有的询问来说，第一个位置上的1完全没有意义，因为r已经在第五个1的右边，对于任何查询的[L,5]区间来说，如果第一个1被算了，那么他完全可以用第五个1来替代。

那么我们将询问按右端点从小到大进行排序利用数据结构维护前缀和涉及的操作有单点修改和区间（前缀和）查询

这样每次我们更新一个点的时候就可以将和他同颜色的上一个点的影响消除即将上一个点所在的位置-1 然后将当前点位置+1

这样问题就解决了qwq

然而这道题对线段树并不友好（可能我写的太丑了加上数据又加强了）T了一个点

经过各种玄学修改比如将结构体换成数组加上inline 甚至在读入优化的基础上加上输出优化还是T掉了qwq

但毕竟也算是正解就挂一下好了

涉及的操作就是单点修改和区间求和了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int M=1e6+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m,s[M];
int last[M],ans[M];
struct node{int l,r,sum;}e[4*M];
struct qwq{int id,l,r;}q[M];
int cmp(qwq x,qwq y){return x.r<y.r;}
void up(int x){e[x].sum=e[x<<1].sum+e[x<<1^1].sum;}
void build(int x,int l,int r){
    e[x].l=l; e[x].r=r;
    if(l==r) return ;
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1^1,mid+1,r);
}
void del(int x,int D){
    if(e[x].l==e[x].r&&e[x].l==D){
        e[x].sum=0;
        return ;
    }
    int mid=e[x].l+e[x].r>>1;
    if(D<=mid) del(x<<1,D);
    if(D>mid) del(x<<1^1,D);
    up(x);
}
void add(int x,int D){
    if(e[x].l==e[x].r&&e[x].l==D){
        e[x].sum=1;
        return ;
    }
    int mid=e[x].l+e[x].r>>1;
    if(D<=mid) add(x<<1,D);
    if(D>mid) add(x<<1^1,D);
    up(x);
}
int p_ans(int x,int L,int R){
    if(L>R) return 0;
    if(L<=e[x].l&&e[x].r<=R) return e[x].sum;
    int ans=0,mid=e[x].l+e[x].r>>1;
    if(L<=mid) ans+=p_ans(x<<1,L,R);
    if(R>mid) ans+=p_ans(x<<1^1,L,R);
    return ans;
}
int main(){
    n=read(); build(1,1,n);
    for(int i=1;i<=n;i++) s[i]=read();
    m=read();
    for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp);
//    for(int i=1;i<=m;i++) printf("qwq%d %d\n",q[i].l,q[i].r);
    int x=1;
    for(int i=1;i<=m;i++){
        while(x<=q[i].r){
            if(last[s[x]]) del(1,last[s[x]]);
            add(1,x); last[s[x]]=x;
            x++;
        }
        ans[q[i].id]=p_ans(1,1,q[i].r)-p_ans(1,1,q[i].l-1);
//        printf("qaq%d\n",x);
        
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

View Code

第二种做法自然就是树状数组了树状数组的常数果然比线段树要小很多跑得飞快

涉及的操作自然就是单点修改和求前缀和了

也算是复习了一波树状数组这里挂一个大大的优秀讲解好了 https://www.cnblogs.com/xenny/p/9739600.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define lowbit(x) x&(-x)
using namespace std;
const int M=1e6+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m,s[M],sum[M*4];
int last[M],ans[M];
struct qwq{int id,l,r;}q[M];
int cmp(qwq x,qwq y){return x.r<y.r;}
void update(int x,int k){
    while(x<=n){
        sum[x]+=k;
        x+=lowbit(x);
    }
}
int p_ans(int x){
    int ans=0;
    while(x){
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) s[i]=read();
    m=read();
    for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int x=1;
    for(int i=1;i<=m;i++){
        while(x<=q[i].r){
            if(last[s[x]]) update(last[s[x]],-1);
            update(x,1); last[s[x]]=x;
            x++;
        }
        ans[q[i].id]=p_ans(q[i].r)-p_ans(q[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

View Code

洛谷 P1972 [SDOI2009]HH的项链——树状数组

推荐阅读