SP3267 DQUERY - D-query
2022/8/1 23:23:09
本文主要是介绍SP3267 DQUERY - D-query,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意:
给出一个长度为n 的数列,\(a_{1},a_{2},...,a_{n}\),有q 个询问,每个询问给出数对 \((i,j)\),需要你给出 \(a_{i},a_{i+1} ,...,a_j\) 这一段中有多少不同的数字
分析:
考虑到树状数组对于处理前缀和问题很方便,自然,尝试用树状数组来进行处理。设 \(tree[i]\) 表示前 \(i\) 个数不同的数的种类数。显然,这样处理是不够的。在计算的过程中,我们也要对 \(tree[i]\) 进行更新。
为了更方便地进行 \(tree[i]\) 的更新,我们将每个询问先保存下来,进行离线操作,按照 \(j\) 的由小到大的顺序进行排序。对于每个区间,尽可能统计其靠近右端点的不同的数的个数,用一个 \(last[i]\) 表示在输入序列下标为 \(i\) 的元素左边第一个值与它相同的元素的下标。对于一个数,它最后出现的位置越靠近当前枚举的右端点越好。以 \(k\) 为枚举的下标,如果 \(a[k]\) 之前有相同的数,那么减掉之前那个数的贡献,加上当前数的贡献。这样就能完成对 \(tree\) 数组的维护。
AC代码:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 5; int n,a[MAXN],tree[MAXN],rec[MAXN],last[MAXN],m,ans[MAXN]; struct askk{ int l,r,pos; }ask[MAXN]; bool cmp(askk aa,askk b){ return aa.r < b.r; } int lowbit(int i){ return i & -i; } void add(int x,int y){ while(x <= n){ tree[x] += y; x += lowbit(x); } } int sum(int x){ int ans = 0; while(x > 0){ ans += tree[x]; x -= lowbit(x); } return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; last[i] = rec[a[i]]?rec[a[i]]:MAXN; rec[a[i]] = i;//维护 last 数组 } cin >> m; for(int i = 1; i <= m; i++){ cin >> ask[i].l >> ask[i].r; ask[i].pos = i; } int k = 1; sort(ask + 1,ask +1 + m,cmp);//对询问排序 for(int i = 1; i <= m; i++){ while(k <= ask[i].r){ add(last[k],-1); add(k,1);//维护tree数组 k++; } ans[ask[i].pos] = sum(ask[i].r) - sum(ask[i].l - 1); } for(int i = 1; i <= m; i++){ cout << ans[i] << "\n"; } }
这篇关于SP3267 DQUERY - D-query的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?