牛客网暑期ACM多校训练营（第一场）J Different Integers

题目链接

题意

长度为N的数组，Q次询问，每次询问给两个数 L,R，求区间 [1, L] 和 [R, N]中一共有几种数
1 <= N, Q <= 1e5
每次最多10个测试数据

AC

• 暴力肯定超时，用树状数组维护
  离线考虑没出现的数字个数假设 r > last[x]，那么当l < first[x] 时，则x 没出现
  有两种实现方式：
  
• 按照查询区间的右端点升序
  当数字最后出现在这个右端点处，那么下面的区间的右侧至少不会出现这个数字，因为下个区间的右端点大于等于上个区间，只用判断左区间就ok
• 按照查询区间的左端点降序
  当数字第一次出现在左端点处，那么下一个区间的左侧至少不会出现这个数字，因为下个区间的左端点小于上个区间，只用判断右区间就ok
• 左端点降序

using namespace std;struct ac{int l, r, id;bool operator <(const ac &x) {return l > x.l;} }; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, q;while (scanf("%d%d", &n, &q) != EOF) {// 记录每个数 开始出现的位置 和 最后出现的位置vector<int> a(n + 1), first(n + 1), last(n + 1);// 统计数字种类int sum = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);last[a[i]] = i;if (!first[a[i]])first[a[i]] = i, sum++;}// queries 存放询问vector<ac> queries(q);for (int i = 0; i < q; ++i) {scanf("%d%d", &queries[i].l, &queries[i].r);queries[i].id = i;}// 按照询问左区间降序sort(queries.begin(), queries.end());// count 记录不在范围中的数// ans 记录每次询问的结果vector<int> count(n + 1), ans(q);for (int i = n, k = 0; i >= 1; --i) {// 枚举每个区间while (k < q && queries[k].l == i) {if (k == q) break;ans[queries[k].id] = sum;// 减去不在区间的数字， 向左枚举for (int j = queries[k].r; j > 0; j -= lowbit(j)) {ans[queries[k].id] -= count[j];}k++;}// 更新不在区间的数字if (first[a[i]] == i) {for (int j = last[a[i]] + 1; j <= n; j += lowbit(j)) {count[j]++;}}}for (int i = 0; i < q; ++i) {printf("%d\n", ans[i]);}}return 0; }

• 右端点升序

using namespace std; struct ac{int l, r, id;bool operator <(const ac &a) {return r < a.r;} }; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, q;while (~scanf("%d%d", &n, &q)) {// 记录每个数 开始出现的位置 和 最后出现的位置vector<int> a(n + 1), last(n + 1), first(n + 1);// 统计数字种类int sum = 0;for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);last[a[i]] = i;if (!first[a[i]]) {first[a[i]] = i;sum++;}}// count 记录不在范围中的数// ans 记录每次询问的结果vector<int> count(n + 1), ans(q);// queries 存放询问vector<ac> queries(q);for (int i = 0; i < q; ++i) {scanf("%d%d", &queries[i].l, &queries[i].r);queries[i].id = i;}// 按照询问右端点升序sort(queries.begin(), queries.end());int k = 0;for (int i = 1; i <= n && k < q; ++i) {while (k < q && queries[k].r == i) {ans[queries[k].id] = sum;// 减去不在区间的数字， 向左枚举for (int j = queries[k].l; j <= queries[k].r; j += lowbit(j)) {ans[queries[k].id] -= count[j];}++k;}// 更新不在区间的数字if (last[a[i]] == i) {for (int j = first[a[i]] - 1; j > 0; j -= lowbit(j)) {count[j]++;}}}for (int i = 0 ; i < q; ++i) {printf("%d\n", ans[i]);}}

总结

以上是生活随笔为你收集整理的牛客网暑期ACM多校训练营（第一场）J Different Integers的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。