请写一份[NOIP2016 DAY1]换教室的代码
时间: 2023-10-11 07:09:40 浏览: 47
好的,以下是一份[NOIP2016 DAY1]换教室的参考代码,供你参考。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000000 + 5;
int n, m;
int a[MAXN], b[MAXN];
int f[MAXN];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int cnt = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) {
int pos = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
f[i] = pos;
}
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
int ans = unique(f + l, f + r + 1) - f;
cout << ans << endl;
}
return 0;
}
```
这个代码的思路是,先将原数组 a 复制到数组 b 中,然后对数组 b 进行排序和去重,得到一个去重后的数组。接着针对原数组 a,将每个元素的值转换为在数组 b 中的排名,存储在数组 f 中。这样做的目的是为了方便后面的查询操作。
对于每个查询操作,我们只需要在数组 f 的 [l, r] 区间内去重,得到区间内不同元素的个数,即为答案。