【题解】HH的项链

HH的项链

前言

如果评测机再好一点,主席树能卡过去(这不是你不会离线树状数组做法的借口!)

解题思路

本题是一道主席树,由于记录的是种数,所以是不满足直接区间加的。

于是就考虑其他的操作:
我们用was记录下当前节点上一个节点的位置,当且仅当was[i]<=l的时候,加入答案。
当当前点的值并不是当前区间的第一个,会重复记录同一个数,不符合题意,故每次记录第一个出现的数字即可。

我们用主席树维护这个was数组即可。
没人知道我在水文章数吧(

代码

#include<bits/stdc++.h>//由于主席树被卡了,所以请不要在意本代码只有65分。
using namespace std;
int n,m;
const int Maxn=3e7;
int a[1000005],li[1000005];
int was[1000005];
int last[1000005];
struct t{
    int ls,rs,sum;
}tree[Maxn];
int root[1000005];
int tot=0;
int build(int l,int r){
    int now=++tot;
    if(l==r)return now;
    int mid=(l+r)/2;
    tree[now].ls=build(l,mid);
    tree[now].rs=build(mid+1,r);
    return now;
}
int modify(int now,int l,int r,int goal,int sum){
    int pos=++tot;
    tree[pos]=tree[now];
    if(l==r){
        tree[pos].sum+=sum;
        return pos;
    }
    int mid=(l+r)>>1;
    if(goal<=mid){
        tree[pos].ls=modify(tree[now].ls,l,mid,goal,sum);
    }
    else if(goal>mid){
        tree[pos].rs=modify(tree[now].rs,mid+1,r,goal,sum);
    }
    tree[pos].sum=tree[tree[pos].ls].sum+tree[tree[pos].rs].sum;
    return pos;
}
int anss=0;
void query(int pos1,int pos2,int gl,int gr,int l,int r){
    if(gl<=l&&r<=gr){
        anss=anss+tree[pos2].sum-tree[pos1].sum;
        return ; 
    }
    int mid=(l+r)>>1;
    if(mid>=gl){
        query(tree[pos1].ls,tree[pos2].ls,gl,gr,l,mid);
    }
    if(mid<gr)query(tree[pos1].rs,tree[pos2].rs,gl,gr,mid+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        was[i]=last[a[i]];
        last[a[i]]=i;
    }
    root[0]=build(0,n);
    for(int i=1;i<=n;i++){
        root[i]=modify(root[i-1],0,n,was[i],1);
    }
    int l,r;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        anss=0;
        query(root[l-1],root[r],0,l-1,0,n);
        cout<<anss<<endl;
    }
    return 0;
} 

本文链接:http://kaispace.com.cn/index.php/archives/672/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者

    jyeric
    jyeric  2020-08-04, 07:56

    我知道你在水文章,因为你代码连个都没有。但是我作为一只鸽子没有资格去指责/kk。