Luogu P1972 [SDOI2009]HH的项链|树状数组
2021/6/28 23:31:36
本文主要是介绍Luogu P1972 [SDOI2009]HH的项链|树状数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目大意:
一个长度为 \(n\) 的序列,第 \(i\) 个数为 \(a_i\),求 \(L\) 和 \(R\) 之间有多少个不同的 \(a_i\) 。
\(1 \le n,m,a_i \le 10^6\)
题解:
又是一个比较有趣的trick。以下部分借鉴于网络。
注意到对于同一区间的一个数,我们可以只关心最后出现的位置。
有一个方法是我们维护每个位置出现的数是否最后一次出现。于是,求前缀和便可知\([1..n]\) 的不同数的个数了。
回到本题,对于每个 \(r_i\) ,我们可以维护 \([1..r_i]\) 时的不同数及此时 \([1..l_i]\)的不同数(注意前面的区间会随着后面数的加入而改变)。考虑到本题不强制在线,这可以通过离线实现。
#include<bits/stdc++.h> #define lowbit(x) x&(-x) #define N 1001000 using namespace std; int vis[N],t[N]; int n,a[N],m; struct data { int L,R,num,ans; }q[N]; bool cmp(data x,data y) { return x.R<y.R; } bool cnp(data x,data y) { return x.num<y.num; } void add(int x,int y) { for (int i=x;i<=n;i+=lowbit(i)) t[i]+=y; } int ask(int x) { int ans=0; for (int i=x;i;i-=lowbit(i)) ans+=t[i]; return ans; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d%d",&q[i].L,&q[i].R); q[i].num=i; } sort(q+1,q+m+1,cmp); for (int i=1,j=1;i<=n;i++) { if (vis[a[i]]) add(vis[a[i]],-1); add(i,1);vis[a[i]]=i; while (i==q[j].R) q[j].ans=ask(q[j].R)-ask(q[j].L-1),j++; } sort(q+1,q+m+1,cnp); for (int i=1;i<=m;i++) { cout<<q[i].ans<<endl; } return 0; }
这篇关于Luogu P1972 [SDOI2009]HH的项链|树状数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现