zcmimi's blog

查看原题

点击跳转

解法

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树

#include<bits/stdc++.h>
const int N=1000011;
int n,q,lst[N],RT[N],sz,s[N*20],ls[N*20],rs[N*20];
void build(int&x,int l,int r){
    x=++sz;
    if(l==r)return;
    int m=l+r>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int&x,int pre,int p,int l,int r){
    s[x=++sz]=s[pre]+1;
    if(l==r)return;
    ls[x]=ls[pre],rs[x]=rs[pre];
    int m=l+r>>1;
    if(p<=m)ins(ls[x],ls[pre],p,l,m);
    else ins(rs[x],rs[pre],p,m+1,r);
}
int ask(int x,int y,int R,int l,int r){
    if(r<=R)return s[y]-s[x];
    int m=l+r>>1;
    return ask(ls[x],ls[y],R,l,m)+(R>m?ask(rs[x],rs[y],R,m+1,r):0);
}
void read(int&x){
    x=0;char c=getchar();
    for(;c<'0'||'9'<c;c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-48;
}
int main(){
    read(n);
    int x,l,r;
    build(RT[0],1,n);
    for(int i=1;i<=n;++i)
        read(x),
        ins(RT[i],RT[i-1],lst[x]+1,1,n),
        lst[x]=i;
    read(q);
    while(q--)
        read(l),read(r),
        printf("%d\n",ask(RT[l-1],RT[r],l,1,n));
}

主席树理论上是可以过的,可是为了卡莫队,主席树也TLE了

R.I.P

树状数组

还是求[l,r]pre_i<l的个数

离线处理

询问按右端点从小到大排序

枚举区间,将[1,r]中的点,i位置+1,pre_i位置-1(i之前pre_i已经贡献过了)

那么r减去l-1的前缀和就是答案

#include<bits/stdc++.h>
const int N=1000011;
int n,m,pre[N],lst[N],s[N],ans[N];
void add(int x,int v){
    for(;x<=n;x+=x&-x)s[x]+=v;
}
int ask(int x){
    int res=0;
    for(;x;x-=x&-x)res+=s[x];
    return res;
}
void read(int&x){
    x=0;char c=getchar();
    for(;'0'<c||c<'9';c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-48;
}
struct que{
    int l,r,id;
    bool operator<(const que&t)const{
        return r<t.r;
    }
}q[N];
int main(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;++i)
        scanf("%d",&x),
        pre[i]=lst[x]?lst[x]:n+1,
        lst[x]=i;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&q[i].l,&q[i].r),
        q[i].id=i;
    std::sort(q+1,q+m+1);
    for(int i=1,j=1;i<=m;++i){
        for(;j<=q[i].r;++j)
            add(j,1),add(pre[j],-1);
        ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1);
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
}
LG 1972 [SDOI2009]HH的项链
comment评论
Search
search