当前位置：首页 > news >正文

【可持久化线段树】 [SDOI2009] HH的项链主席树（两种解法）

news 来源：原创 2025/6/8 19:59:19

文章目录

1.题目描述
2.思路
3.解法一
- 解法一代码
4.解法二
- 解法二代码（版本一）
- 解法二代码（版本二）

1.题目描述

原题：https://www.luogu.com.cn/problem/P1972
[SDOI2009] HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 $n$ ，表示项链长度。
第二行 $n$ 个正整数 $a_i$ ，表示项链中第 $i$ 个贝壳的种类。

第三行一个整数 $m$ ，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l, r$ ，表示询问的区间。

输出格式

输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

样例 #1
样例输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出 #1

2
2
4

提示

【数据范围】

对于 $20\%$ 的数据， $1\le n,m\leq 5000$ ；
对于 $40\%$ 的数据， $1\le n,m\leq 10^5$ ；
对于 $60\%$ 的数据， $1\le n,m\leq 5\times 10^5$ ；
对于 $100\%$ 的数据， $1\le n,m,a_i \leq 10^6$ ， $1\le l \le r \le n$ 。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB

2.思路

对于多个查询区间 ([l, r]) 中，如果它们的右端点 (r) 相同，那么项链中每个数字只需考虑其在 (r) 位置之前的最后一次出现。
考虑项链序列：1 3 1 3 4 1 2

对于所有以 (r = 7) 为右端点的查询：

第一个位置和第三个位置的 1 可以忽略，因为最后一个 1 出现在第六个位置。
同样，第二个位置的 3 也可以忽略，因为最后一个 3 出现在第四个位置。

因此，对于任何查询 ([l, 7])，只需统计第六个位置的 1、第四个位置的 3、第五个位置的 4 和第七个位置的 2。这样，重复出现的数字只需考虑其最新的位置，从而简化了计算过程。

所以该题可以用树状数组，线段树，可持续化线段树等等很多种方法解决，接下来我将使用主席树解决。

3.解法一

每个版本只记录到当前位置的所有数的最后一次出现的位置

构建持久化线段树：
- 遍历项链中的每个贝壳：
  - 如果该贝壳是第一次出现，直接在当前版本的线段树上添加该位置。
  - 如果该贝壳之前出现过，则先将创建一个临时变量rt,在rt中将 a[i] 上一次出现的位置从线段树中移除，再通过rt将当前的位置添加到新版线段树中。
- 每次修改线段树时，生成一个新的版本，以便后续查询使用。
处理查询：
- 对于每个查询 ([l, r])，利用版本 (r) 的线段树查询区间 ([l, r]) 内的不同贝壳种类数量，到达 ([l, l])叶子结点累加起来的就是答案，因为我们每个版本只记录了 ([1, r]) 的每个数最后出现的位置，所以直接返回 ([l, r])的sum值即可。

该代码的思路比较简单，但常数比较大，必须使用快读才能过

解法一代码

#include<bits/stdc++.h>using namespace std;
const int N = 1e6+10;
int ls[N*40],rs[N*40],sum[N*40];
int last[N];//a[i]最后一次出现的位置 
int root[N],a[N];
int tot;int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];
}
void change(int &u,int v,int l,int r,int p,int k){u = ++tot;ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v]+k;if(l==r){return;}int mid =l+r>>1;if(p<=mid)change(ls[u],ls[v],l,mid,p,k);else change(rs[u],rs[v],mid+1,r,p,k);
}int query(int u,int l,int r,int lm){if(l==r)return sum[u];int mid =l+r>>1;if(lm<=mid) return query(ls[u],l,mid,lm)+sum[rs[u]];else return query(rs[u],mid+1,r,lm);
}int n,m,l,r,rt;
int main(){n=read();for(int i=1;i<=n;i++){a[i]=read();if(!last[a[i]]){//a[i]第一次出现，直接添加新的分支 change(root[i],root[i-1],1,n,i,1);}else{//a[i]已经出现过，则把上一次出现叶子结点的位置置为0 //再创建当前版本，每个版本只保留每个数最后一次出现的位置为1 change(rt,root[i-1],1,n,last[a[i]],-1);change(root[i],rt,1,n,i,1);}last[a[i]]=i;} m=read();int l,r;while(m--){l=read(),r=read();printf("%d\n",query(root[r],1,n,l));}return 0;
}

4.解法二

树内维护颜色（数字）的前一次出现位置

在第一种方法中，我们直接统计区间内不同数字的数量。第二种方法我们在持久化线段树中记录每个数字在当前位置之前的最后一次出现位置。如果某个数字在当前位置之前从未出现过，那我们假设它在位置 0 处出现过，线段树中维护的权值区间为 [0, n]。

线段树版本与叶子结点的含义

考虑第 ver 版本的线段树 root[ver]：

叶子结点的表示：
- 对于某个叶子结点 pos，如果其值为 1，表示在序列区间 [pos + 1, ver] 中存在一个位置 x，满足 a[x] == a[pos]。
例如：
- 项链序列：1 3 1 3 4 1 2
- 对于 ver = 7，如果 pos = 1，叶子结点值为 1 表示在 [2, 7] 区间内存在颜色 1 的位置 x（如 x = 3 和 x = 6）。

处理查询区间 [l, r]

其实就是询问对于L<=i<=R,满足last[i]<l的个数。

对于每个位置 pos，如果 root[r]中的 pos 位置值为 1，表示在 [pos + 1, r] 区间内存在一个位置
x，使得 a[x] == a[pos]。如果这个位置 x 位于查询区间 [l, r] 内，则 x 对答案有贡献。
使用root[r] 和 root[l - 1] 版本的线段树信息，查询 [0, l - 1] 区间内的叶子结点。计算root[r] 和 root[l - 1] 的sum（这个区间内标记的总数）的差，得到在 [l, r] 区间内对答案有贡献的位置 x 的数量，这个结果就是我们想要的答案。
再解释，在[l,r]内在出现的不管了吗？答：必然的，因为在这个区间内就意味着他在这个区间已经出现过了，在[0,l-1]内 root[l-1].sum 相当于出现在[1,l-1]内所有数的个数，root[r].sum,相当于出现在[1,l-1]内的所有数的个数 + 在[l,r]内首次出现的数的个数。相减就是答案。
其实直接在r版本query 在[0,l-1]的sum即可，query出来的值减去原数组[1,l-1]内的数的个数（即l-1）即可（饶了半天）。

解法二代码（版本一）

这种方法相对解法一时间复杂度和空间复杂度上都有优化

//last[i]表示位置i的这个数上一次出现的位置（如果没有就是0） 那么对于每次询问L~R范围里的数字种数 ，
//其实就是询问对于L<=i<=R,满足last[i]<L的个数。
//对last造N棵值域线段树询问就直接找到L-1这个位置看它前面有几个 #include<bits/stdc++.h>using namespace std;
const int N = 1e6+10;
int ls[N*22],rs[N*22],sum[N*22];
//last[i]表示i位置上的数上次出现的位置，
//t[i]表示 i这个数最后一次出现的位置 
int last[N],t[N];
int root[N],a[N];
int tot;int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}void change(int &u,int v,int l,int r,int p,int k){u = ++tot;ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v]+k;if(l==r){return;}int mid =l+r>>1;if(p<=mid)change(ls[u],ls[v],l,mid,p,k);else change(rs[u],rs[v],mid+1,r,p,k);
}int query(int u,int v,int l,int r,int lm){if(r<=lm)return sum[u]-sum[v];int mid =l+r>>1;if(lm<=mid) return query(ls[u],ls[v],l,mid,lm);else return sum[ls[u]]-sum[ls[v]]+query(rs[u],rs[v],mid+1,r,lm);
}int n,m,l,r,rt;
int main(){n=read();for(int i=1;i<=n;i++){a[i]=read();last[i]=t[a[i]];t[a[i]]=i;}for(int i=1;i<=n;i++)change(root[i],root[i-1],0,n,last[i],1);m=read();int l,r;while(m--){l=read(),r=read();printf("%d\n",query(root[r],root[l-1],0,n,l-1));}return 0;
}

解法二代码（版本二）

//last[i]表示位置i的这个数上一次出现的位置（如果没有就是0） 那么对于每次询问L~R范围里的数字种数 ，
//其实就是询问对于L<=i<=R,满足last[i]<L的个数。
//对last造N棵值域线段树询问就直接找到L-1这个位置看它前面有几个 #include<bits/stdc++.h>using namespace std;
const int N = 1e6+10;
int ls[N*22],rs[N*22],sum[N*22];
//last[i]表示i位置上的数上次出现的位置，
//t[i]表示 i这个数最后一次出现的位置 
int last[N],t[N];
int root[N],a[N];
int tot;int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}void change(int &u,int v,int l,int r,int p,int k){u = ++tot;ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v]+k;if(l==r){return;}int mid =l+r>>1;if(p<=mid)change(ls[u],ls[v],l,mid,p,k);else change(rs[u],rs[v],mid+1,r,p,k);
}int query(int u,int l,int r,int lm){if(r<=lm)return sum[u];int mid =l+r>>1;if(lm<=mid) return query(ls[u],l,mid,lm);else return sum[ls[u]]+query(rs[u],mid+1,r,lm);
}int n,m,l,r,rt;
int main(){n=read();for(int i=1;i<=n;i++){a[i]=read();last[i]=t[a[i]];t[a[i]]=i;}for(int i=1;i<=n;i++)change(root[i],root[i-1],0,n,last[i],1);m=read();int l,r;while(m--){l=read(),r=read();printf("%d\n",query(root[r],0,n,l-1)-(l-1));}return 0;
}