离线+树状数组维护
题面
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式
M 行，每行一个整数，依次表示询问对应的答案。
题解
这题似乎可以用莫队？？？不过我不会QAQ
思路大致是这样的:
树状数组维护一个前缀和f[i],代表从第一个位置到$i$个位置有多少个不同的数。
于是发现区间不同的值不好维护，我们可以把它离线下来。
我们按询问区间的右端点从小到大排序，之后从第一个数据开始处理。一旦后面的值和前面的值相同，那么在询问包含这个数的区间的时候，后面的值完全可以把前面的值替换掉。
例如
1 2 1 4 3 5
- 在第1位插入
1(表示第一位有一个不一样的数)，标记1 - 在第2位插入
1，标记2 - 在第3位插入
1，发现已被标记，于是清除第一位的1 - 询问1~3，
sum(3) - sum(0)
因为我们询问的区间已按右端点排过序，所以询问的区间不管包不包含已删掉的元素，答案都只被最后一个相同的元素影响。
有点啰嗦了，感性理解一下吧。
代码
#include <bits/stdc++.h>
#define endl '\n'
#define R register
#define lowbit(x) x & -x
using std::cin;
using std::cout;
const int maxn = 1000005;
int a[maxn], b[maxn], n;
int next = 1, vis[maxn], ans[maxn], m;
inline void add(int pos, int x)
{
for (R int i = pos; i <= n; i += lowbit(i))
a[i] += x;
}
inline int sum(int pos)
{
int ans = 0;
for (R int i = pos; i > 0; i -= lowbit(i))
ans += a[i];
return ans;
}
struct ask
{
int l, r, pos;
bool operator<(const ask &b) const
{
return r < b.r;
}
} q[maxn];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (R int i = 1; i <= n; i++)
cin >> b[i];
cin >> m;
for (R int i = 1; i <= m; i++)
{
cin >> q[i].l >> q[i].r;
q[i].pos = i; //记录这个询问的位置
}
std::sort(q + 1, q + m + 1);
for (R int i = 1; i <= m; i++)
{
for (R int j = next; j <= q[i].r; j++)
{
if (vis[b[j]])
add(vis[b[j]], -1); //打上-1是清零：1 + (-1)=0
vis[b[j]] = j;
add(j, 1);
}
ans[q[i].pos] = sum(q[i].r) - sum(q[i].l - 1); //离线计算答案
next = q[i].r + 1;
}
for (R int i = 1; i <= m; i++)
cout << ans[i] << endl;
return 0;
}
Comments NOTHING