P1972 [SDOI2009]HH的项链（树状数组离线，主席树）

本文主要是介绍P1972 [SDOI2009]HH的项链（树状数组离线，主席树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
多次询问 $[l, r]$ 中有多少不同的数。

思路：
本题卡了莫队。

树状数组离线：每个点代表这个位置的值，然后每次遇到这个数，就把上次的位置清空。这样当前维护的区间里面就没有重复数了。

可持久化线段树：其实和树状数组离线一样，就是基于上一个前缀的线段树，将当前位置的值设置为 $a [i]$ ，同时将 $a [i]$ 上一次出现的位置的值减去 $a [i]$ 。

可持久化线段树

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>using namespace std;const int maxn = 1e6 + 7;
struct Tree {int l,r;int sum;
}t[maxn * 40];int a[maxn],pre[maxn];
int tot,T[maxn];int build(int l,int r) {int pos = ++tot;t[pos].sum = t[pos].l = t[pos].r = 0;if(l < r) {int mid = (l + r) >> 1;t[pos].l = build(l,mid);t[pos].r = build(mid + 1,r);}return pos;
}int update(int pre,int x,int v,int l,int r) {int pos = ++tot;t[pos].l = t[pre].l;t[pos].r = t[pre].r;t[pos].sum = t[pre].sum + v;if(l < r) {int mid = (l + r) >> 1;if(x <= mid) {t[pos].l = update(t[pos].l,x,v,l,mid);} else {t[pos].r = update(t[pos].r,x,v,mid + 1,r);}}return pos;
}int query(int pre,int l,int r,int x) {if(l == r) {return t[pre].sum;}int m = (l + r) >> 1;if(x <= m) {return query(t[pre].l,l,m,x) + t[t[pre].r].sum;} else {return query(t[pre].r,m + 1,r,x);}return 0;
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}T[0] = build(1,n);for(int i = 1;i <= n;i++) {if(!pre[a[i]]) {T[i] = update(T[i - 1],i,1,1,n);} else {int t = update(T[i - 1],pre[a[i]],-1,1,n);T[i] = update(t,i,1,1,n);}pre[a[i]] = i;}int q;scanf("%d",&q);while(q--) {int x,y;scanf("%d%d",&x,&y);printf("%d\n",query(T[y],1,n,x));}return 0;
}

树状数组离线

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;typedef long long ll;
const int maxn = 1e6 + 7;struct Node {int l,r;int id;
}q[maxn];int n;
int a[maxn],pre[maxn];
ll ans[maxn],c[maxn];void add(int x,int v) {while(x <= n) {c[x] += v;x += x & -x;}
}ll query(int x) {ll res = 0;while(x) {res += c[x];x -= x & -x;}return res;
}int cmp(Node a,Node b) {return a.r < b.r;
}int main() {scanf("%d",&n);vector<int>vec;for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);vec.push_back(a[i]);c[i] = 0;pre[i] = 0;}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());int m;scanf("%d",&m);for(int i = 1;i <= m;i++) {scanf("%d%d",&q[i].l,&q[i].r);q[i].id = i;}sort(q + 1,q + 1 + m,cmp);int j = 1;for(int i = 1;i <= n;i++) {int now = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1;if(pre[now]) {add(pre[now],-1);}add(i,1);pre[now] = i;for(;j <= m;j++) {if(q[j].r != i) break;ans[q[j].id] = query(q[j].r) - query(q[j].l - 1);}}for(int i = 1;i <= m;i++) {printf("%lld\n",ans[i]);}return 0;
}