问题：给出一个长度为n(1<=n<=1e5)的序列，接下来有q(1<=q<=1e5)个查询，每次查询给出一个区间[l,r],你需要输出在区间[l,r]里有几个不同的数。
解决这个问题的方法，目前就我所知道的有三种。
一、树状数组+离线
首先我们把所有查询一次性读入，然后按照每个查询的r值升序排序（为什么要这样后面会讲到），然后还需要开一个vis数组，vis[i]代表i这个数字上一次出现的位置（如果序列里的数很大的话，可以先离散化一下，我这里先假设序列里的数都不超过1e5），vis初值都为0。
接下来说一下树状数组的作用，众所周知，树状数组可以方便的动态维护一个序列的区间和（不会的同学可以先去学一下 很简单）。我们考虑一个区间[l,r]里的每个位置i，如果a[i]这个数是第一次出现即vis[a[i]]为0，那么我在树状数组里在i这个位置上+1，并且令vis[a[i]] = i。如果a[i]在前面出现过即vis[a[i]]!=0,那么我在树状数组里把vis[a[i]]这个位置上的数-1，并且令vis[a[i]]=i。这样操作完一遍后，你会发现在这个区间里的1的个数就是这个区间里不同的数的个数。所以接下来的工作就是数1有几个，因为我们用树状数组维护过了前缀和，所以直接查询 sum(1，r) - sum(1，l-1)就得到了[l,r]这个区间的和 即1得个数。
上面说了对一个区间的做法，但是如果对每个区间都这样做一次复杂度显然爆炸。所以这里我们需要设一个指针p,初值为1代表从序列的第一个位置开始。因为我们之前已经对区间排过序了，所以我们依次去考虑每个区间，因为后面的区间的r值是大于等于我当前处理的这个区间的r值的，所以用树状数组维护的时候不会影响到后面的区间。每次处理完一个区间后将指针p移动到r+1处即可。因为指针p的总移动次数不超过n次，并且每次的查询和更新是用树状数组维护的，每次的复杂度为log(n),所以总的复杂度为nlog(n)。
下面是具体实现代码，关键代码后面我都跟了注释。
const int N = 1e5 + 10;
int c[N];
int n;
void add(int x, int y) {
for (; x <= n; x += lowbit(x)) {
c[x] += y;
}
}
int query_sum(int x) {
int sum = 0;
for (; x; x -= lowbit(x)) {
sum += c[x];
}
return sum;
}
struct MM {
int id, l, r;
bool friend operator<(const MM& m1, const MM& m2) {
return m1.r < m2.r;
}
}qr[N];
int ans[N];
int a[N];
int vis[N];
int main() {
scanf("%d", &n);
memset(vis,0,sizeof vis);
for (int i = 1; i <= n; i++)scanf("%d", a + i);
int q; scanf("%d", &q);
for (int i = 1; i<=q; i++) {
scanf("%d%d", &qr[i].l, &qr[i].r);
qr[i].id = i;//因为是离线做法，所以需要记录这个区间是第几个查询
}
sort(qr + 1, qr + 1 + q);//按照r值升序排序
int p = 1;//指针初值从1开始
for (int i = 1; i <= q; i++) {
for (int j = p; j <= qr[i].r; j++) {
if (vis[a[j]]) {//判断a[j]在前面是否出现过
add(vis[a[j]], -1);//将a[j]上一次出现的位置上-1（其实本质就是把上次的+1减回来）
}
add(j, 1);//a[j]最新出现的位置上+1
vis[a[j]] = j;//记录a[j]这次出现的位置为j
}
p = qr[i].r + 1;//指针移动
ans[qr[i].id] = query_sum(qr[i].r) - query_sum(qr[i].l - 1);//保存答案
}
for (int i = 1; i <= q; i++)printf("%d\n", ans[i]);
}二、莫队+离线
其实莫队算法本身就是一个离线算法，它比较适合解决一类离线区间询问问题。按照我的理解的话，通俗点讲莫队算法相对于上面那个方法来说就是一个暴力，但是它是一个优美的暴力。它的精妙之处就在于利用了分块的思想，没错就是和数据结构里对序列分块进行处理原理上是一样。对于这道题来讲，一个区间[l,r]如果用一个数组cnt[i]来保存了这个区间里的每个数字出现了几次，那么转移到[l+1,r],[l-1,r],[l,r-1],[l,r+1]这四种情况我们显然可以O(1)的进行转移（废话）。那么对于一般的转移到一个［newl,newr］的复杂度是abs(newl-l)+abs(newr-r)。也就是至始至终的维护cnt数组,去计算每个数字出现几次。（这算什么算法...不就是暴力嘛
如果就按照我们之前讲的那样去暴力转移的话复杂度也是显然爆炸的。下面就是莫队算法的精妙之处，先将这个序列分块，我们假设每一块的大小为S。然后我们离线保存这q个查询，对于每一个[li,ri]按照li所在的块的编号（即(li-1)/S）为第一关键字，ri为第二关键字进行排序。（没错又是排序，可以说是离线做的一个套路）。这样排完序后有什么好处呢？我们依次考虑每个询问[l,r],它转移到下一个区间时是怎么样的：
当下一个区间的左端点和我当前区间的左端点在同一块时：
右端点只会往右移动，因此移动至多为n，总共有 S/n块，所以总的时间复杂度为 O((n/S) * n)
每次询问左端点只会块内移动，因此至多移动 S ，总共有 q 次询问，总复杂度 O(S*q)。
当下一个区间的左端点和我当前区间的左端点不在同一块时：
左右端点移动和为 O(n) ，最多发生n/S次，总复杂度为O((n/S) * n)。
所以总的时间复杂度为O(n * n/S + q * S),当S取n/sqrt(q)时，取得最优复杂度为O(n*sqrt(m))。
这里其实还有一个优化，就是排序的时候把奇数块的r值按照升序排，偶数块的r值降序排。原理就是右指针跳完奇数块，往回跳的时候，顺便把偶数块跳完，然后再跳下一块奇数块。（猛（ka）男(chang)必备
具体实现代码：
const int N = 1e5 + 10;
int a[N], cnt[N];
int S;
struct MM {
int id, l, r;
bool friend operator<(const MM& m1, const MM& m2) {
int b1 = m1.l / S, b2 = m2.l / S;
//return (b1 ^ b2) ? b1 < b2 : ((b1 & 1) ? m1.r<m2.r : m1.r>m2.r);
if (b1 == b2) {//奇偶排序优化
if (b1 & 1)return m1.r < m2.r;
else return m1.r > m2.r;
}
else {
return b1 < b2;
}
}
}qr[N];
int n;
int ans[N];
int nl, nr, now;//[nl,nr]为当前区间，now当前区间的答案
void add(int x) {
if (cnt[x] == 0)++now;
++cnt[x];
}
void del(int x) {
if (cnt[x] == 1)--now;
--cnt[x];
}
void move(int tl, int tr) {//移动到[tl,tr]
//要注意先加再删,否则删一个不存在的数会出错
while (nr < tr)add(a[++nr]);
while (nl > tl)add(a[--nl]);
while (nr > tr)del(a[nr--]);
while (nl < tl)del(a[nl++]);
}
int main() {
scanf("%d", &n);
memset(cnt, 0, sizeof cnt);
for (int i = 1; i <= n; i++)scanf("%d", a + i);
int q; scanf("%d", &q);
S = n / sqrt(q);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &qr[i].l, &qr[i].r);
qr[i].id = i;
}
sort(qr + 1, qr + 1 + q);
nl = 1, nr = 0, now = 0;
for (int i = 1; i <= q; i++) {
move(qr[i].l, qr[i].r);
ans[qr[i].id] = now;
}
for (int i = 1; i <= q; i++)printf("%d\n", ans[i]);
}
对于此题莫队其实还支持动态的查询，但是个人感觉遇到动态的题目时，莫队不是一个首选的解题思路（复杂度不是较优容易被卡）。
三、主席树在线查询
留坑待补...
2020.7.12
牛客多校自闭
重新学了一遍主席树
思路就是对原序列的每一个前缀建出当前版本的树，如果当前这个位置上的数在前面出现过就把那个数之前所在的位置上-1，在当前这个位置上+1
所以整个树维护的就是一些0 1序列的和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
inline ll rd() {
ll x = 0, f = 1; char ch = getchar();
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const double eps = 1e-6;
const int M = 2e6 + 10;
const int N = 2e6 + 10;
vector<int>v;
int a[N];
int n;
void discreat() {
for (int i = 1; i <= n; i++)v.pb(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
inline int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
struct Node {
int l, r, sum;
}t[N << 5];
int root[N], tot;
void insert(int& now, int pre, int l, int r, int pos, int val) {
t[++tot] = t[pre];
now = tot;
t[now].sum += val;
if (l == r)return;
int mid = (l + r) >> 1;
if (pos <= mid)insert(t[now].l, t[pre].l, l, mid, pos, val);
else insert(t[now].r, t[pre].r, mid + 1, r, pos, val);
}
int query(int ql, int qr, int l, int r, int rt) {
if (ql == l && qr == r)return t[rt].sum;
int mid = (l + r) >> 1;
if (qr <= mid)return query(ql, qr, l, mid, t[rt].l);
else if (ql > mid)return query(ql, qr, mid + 1, r, t[rt].r);
else return query(ql, mid, l, mid, t[rt].l) + query(mid + 1, qr, mid + 1, r, t[rt].r);
}
int last[N];
int main() {
n = rd();
int q = rd();
for (int i = 1; i <= n; i++)a[i] = rd();
//discreat();
for (int i = 1; i <= n; i++) {
if (last[a[i]]) {
insert(root[i], root[i - 1], 1, n, last[a[i]], -1);
insert(root[i], root[i], 1, n, i, 1);
}
else {
insert(root[i], root[i - 1], 1, n, i, 1);
}
last[a[i]] = i;
}
while (q--) {
int l = rd(), r = rd();
printf("%d\n", query(l, r, 1, n, root[r]));
}
}
京公网安备 11010502036488号