脚本宝典收集整理的这篇文章主要介绍了P1972 [SDOI2009]HH的项链（离线+树状数组 / 主席树），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目链接 题目描述： HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。 有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式: 一行一个正整数 (n)，表示项链长度。 第二行 (n) 个正整数 (a_i)，表示项链中第(i)个贝壳的种类。 第三行一个整数 (m)，表示HH询问的个数。 接下来(m)行，每行两个整数(l,r)，表示询问的区间。
思路：
第一眼，可以用莫队处理，但是这道题卡莫队
离线+树状数组：先将所有询问保存，按左端点(l)为第一关键词，右端点(r)为第二关键词进行排序。树状数组中保存的是原数组下标对应元素个数，而不是数的大小序号对应元素个数。对区间([l_1、l_2 、、l_k,r])进行查询，则需遍历(a_1、a_2、...、a_r)，对树状数组不断更新，对于重复元素，只保留最靠近右端点r的值。则区间([l_i,r])内不同元素个数为树状数组中大小在区间([i,r])的数的个数。
主席树：数组中不同位置保存不同版本的线段树，同样的，线段树中保存的也是原数组下标对应元素个数，对于重复元素，只保留最靠近当前点(i)的值，删除之前相同元素位置的值。对区间([l,r])进行查询，则在(root[r])版本的线段树中查询区间([i,r])(也可以是区间([i,n])，因为在根结点为(root[r])的线段树中，区间([r+1,n])没有进行更新，即都为(0))的元素和。
code: 离线+树状数组
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorIThm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <;map>
#include <set>
#include <unordered_map>
#define fi First
#define se second
#define pb push_back
// #define endl "n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freoPEn(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
using namespace std;
ll read(){
char ch = 'a'; ll f = 1, y = 0;
while(ch < '0' || ch > '9')ch = getchar();
if(ch == '-')f = -1;
while(ch >= '0' && ch <= '9')y = y * 10 + ch - '0', ch = getchar();
return f * y;
}
inline void write(ll a){
if(a > 9)write(a / 10);
putchar(a % 10 + '0');
}
struct node{
int l, r, id;
bool operator<(const node & a)const{
return (r == a.r) ? l < a.l : r < a.r;
}
}p[maxn];
int n, m, s[maxn], ans[maxn];
int c[maxn << 2], PRe[maxn];
void update(int x, int v){
for(int i = x; i <= n; i += lowbit(i))c[i] += v;
}
int getsum(int x){
int ret = 0;
for(int i = x; i; i -= lowbit(i))ret += c[i];
return ret;
}
int main(){
n = read();
for(int i = 1; i <= n; i ++)s[i] = read();
m = read();
for(int i = 1; i <= m; i ++){
p[i].l = read(), p[i].r = read();
p[i].id = i;
}
sort(p + 1, p + m + 1);
int j = 1;
for(int i = 1; i <= n; i ++){
if(!pre[s[i]])update(i, 1);
else update(pre[s[i]], -1), update(i, 1);
for(; p[j].r == i; j ++){
ans[p[j].id] = getsum(i) - getsum(p[j].l - 1);
}
pre[s[i]] = i;
}
for(int i = 1; i <= m; i ++)write(ans[i]), puts("");
return 0;
}
主席树
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <unordered_map>
#define fi first
#define se second
#define pb push_back
// #define endl "n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
using namespace std;
inline ll read(){
char ch = 'a'; ll f = 1, y = 0;
while(ch < '0' || ch > '9')ch = getchar();
if(ch == '-')f = -1;
while(ch >= '0' && ch <= '9')y = y * 10 + ch - '0', ch = getchar();
return f * y;
}
inline void Write(ll a){
if(a > 9)Write(a / 10);
putchar(a % 10 + '0');
}
struct node{
int l, r, v;
}t[maxn * 50];
int n, m, p[maxn], pre[maxn];
int tot, root[maxn];
int build(int l, int r){
int rt = ++ tot;
if(l == r)return rt;
int mid = l + r >> 1;
t[rt].l = build(l, mid), t[rt].r = build(mid + 1, r);
return rt;
}
int update(int node, int l, int r, int v, int pos){
int rt = ++ tot;
t[rt] = t[node], t[rt].v += v;
if(l == r)return rt;
int mid = l + r >> 1;
if(pos <= mid)t[rt].l = update(t[rt].l, l, mid, v, pos);
else t[rt].r = update(t[rt].r, mid + 1, r, v, pos);
return rt;
}
int query(int rt, int l, int r, int pos){
if(l == r)return t[rt].v;
int mid = l + r >> 1, ret = 0;
if(pos <= mid)ret += query(t[rt].l, l, mid, pos) + t[t[rt].r].v;
else ret += query(t[rt].r, mid + 1, r, pos);
return ret;
}
int main(){
n = read();
for(int i = 1; i <= n; i ++)p[i] = read();
root[0] = build(1, n);
for(int i = 1; i <= n; i ++){
if(!pre[p[i]])root[i] = update(root[i - 1], 1, n, 1, i);
else{
int t = update(root[i - 1], 1, n, -1, pre[p[i]]);
root[i] = update(t, 1, n, 1, i);
}
pre[p[i]] = i;
}
m = read();
int l, r;
for(int i = 1; i <= m; i ++){
l = read(), r = read();
int ans = query(root[r], 1, n, l);
Write(ans), puts("");
}
return 0;
}
以上是脚本宝典为你收集整理的P1972 [SDOI2009]HH的项链（离线+树状数组 / 主席树）全部内容，希望文章能够帮你解决P1972 [SDOI2009]HH的项链（离线+树状数组 / 主席树）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。