刷题记录:牛客NC20325[SDOI2009]HH的项链

传送门:牛客

题目描述:

HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一 段贝壳，思考它们所表达的含义。
HH不断地收集新的贝壳，因此他的项链变得越来越长。
有一天，他突然提出了一 个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答。。。因为项链实在是太长了。于是，他只 好求助睿智的你，来解决这个问题
输入:
6
1 2 3 4 3 5
3
1 2 
3 5
2 6
输出:
2
2
4

对于本题,我们发现可以进行这样的一个转化.假设我们找出了一个数字前一次出现的地方,用$last[]$记录,那么对于一个询问区间$[l,r]$来说,此时我们只需要找出区间内有几个数字的$last$值是小于$l$即可.那么此时我们需要解决的问题就是:
$$\sum _{i=l}^{r}last[i]<l$$
这是一个主席树的经典模型,直接套主席树即可解决

对于主席树(可持久化线段树),网上有大量的博客讲解(不乏有详细的),此处就不在赘述了.

但是对于此题来说,比较麻烦的是此时我们又出现了0这样的数字,总所周知,朴素的主席树用的是权值线段树的思想,此时我们是无法维护0的.所以我们需要将所有数字的位置都往后移动一位,也就是将2当做我们的贝壳的开始,此时就可以进行维护了

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000010
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int last[maxn];
int n,m;
struct PerSegment_tree {int l,r,lnum,rnum,sum;
}tree[maxn<<5];int cnt=0;int RT[maxn];
int build(int l,int r) {int p=++cnt;tree[p].l=l;tree[p].r=r;if(l==r) return p;int mid=(l+r)>>1;tree[p].lnum=build(l,mid);tree[p].rnum=build(mid+1,r);return p;
}
int update(int pre,int val) {int p=++cnt;tree[p]=tree[pre];tree[p].sum+=1;if(tree[p].l==tree[p].r) return p;int mid=(tree[p].l+tree[p].r)>>1;if(val<=mid) tree[p].lnum=update(tree[pre].lnum,val);else tree[p].rnum=update(tree[pre].rnum,val);return p;
}
ll query(int pre,int now,int l,int r,int k) {if(l==r) return tree[now].sum-tree[pre].sum;int mid=(l+r)>>1;if(k<=mid) return query(tree[pre].lnum,tree[now].lnum,l,mid,k);else {int s=tree[tree[now].lnum].sum-tree[tree[pre].lnum].sum;return (ll)s+query(tree[pre].rnum,tree[now].rnum,mid+1,r,k);}
}
int main() {n=read();for(int i=1;i<=n+1;i++) last[i]=1;RT[1]=build(1,n+1);for(int i=2;i<=n+1;i++) {int a=read();RT[i]=update(RT[i-1],last[a]);last[a]=i;}m=read();for(int i=1;i<=m;i++) {int l=read(),r=read();l++;r++;printf("%lld\n",query(RT[l-1],RT[r],1,n+1,l-1));}return 0;
}