Codeforces Round #261 (Div. 2) D 树状数组应用
2023-09-14 09:08:17 时间
看着题意:[1,i]中等于a[i]的个数要大于[,jn]中等于a[j]的个数 且i<j,求有多少对这种(i,j) ,i<j可是 i前面的合法个数 要大于j后面的 看起来非常像逆序数的样子,所以非常easy往树状数组想去,可是处理就看个人了,像我比赛的时候就处理得非常的麻烦,虽做出了可是花时间也多,经过杰哥的教育,事实上正着塞进树状数组 反着来找就能够了,灰常的简单清晰明了,贴一发纪念我的搓比...
int n; int aa[1000000 + 55]; int bb[1000000 + 55]; int c[1000000 + 55]; map<int ,int > mp; ll lowbit(ll x) { return x&(-x); } void add(int i,int val) { while(i <= n) { c[i] += val; i += lowbit(i); } } ll get_sum(int i) { ll sum = 0; while(i) { sum += c[i]; i -= lowbit(i); } return sum; } void init() { memset(c,0,sizeof(c)); memset(aa,0,sizeof(aa)); memset(bb,0,sizeof(bb)); mp.clear(); } int main() { while(scanf("%d",&n) == 1) { init(); for(int i=1;i<=n;i++)scanf("%d",&aa[i]); for(int i=1;i<=n;i++) { mp[aa[i]]++; bb[i] = mp[aa[i]]; add(bb[i],1); } mp.clear(); ll ans = 0ll; for(int i=n;i>=1;i--) { add(bb[i],-1); mp[aa[i]]++; int tmp = mp[aa[i]]; ans += i - get_sum(tmp) - 1; } cout<<ans<<endl; } return 0; }
相关文章
- hdu3746 KMP-next数组的应用
- 大数据应用电子商务之精准推广
- 应用实时监控服务 ARMS 4 月功能新鲜快报
- 用Spring Boot颠覆Java应用开发
- 【原创】多线程应用中pthread库使用问题
- SAP CAP Fiori Elements 应用配置 UI 的两种方式以及自定义 index.html
- android studio运行应用执行代码流程
- C++:C++编程语言学习之数组/指针的简介、案例应用之详细攻略
- DataScience&ML:金融科技领域之迁徙率(Flow Rate)表的简介、案例应用之详细攻略
- DL框架:主流深度学习框架(TensorFlow/Pytorch/Caffe/Keras/CNTK/MXNet/Theano/PaddlePaddle)简介、多个方向比较、案例应用之详细攻略
- 【JavaEE基础与高级 第6章】JavaEE中的二维数组详细介绍与应用
- 零代码,让业务人员实现应用创造自由
- Qt5.9/C++架构实例(一个简单的MCV架构应用实例)
- C#开发的OpenRA的Enumerable.Concat方法应用
- 二分法应用——搜索旋转数组,以前一直在纠结a[0],a[-1],a[mid], target三者关系,其实最简单的还是使用2次二分,先找到旋转数组peak,然后用正常的二分搜索即可!
- 结构体数组应用举例
- 腾讯云GPU服务器规格应用场景选择说明
- 二维数组的应用之---三子棋(精简版)详解