【算法模板】离线树状数组(区间查询小于等于x的数个数)
2022/4/18 22:12:34
本文主要是介绍【算法模板】离线树状数组(区间查询小于等于x的数个数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
只需要把询问按x升序排序,在查询的过程中不断让树状数组把<=x元素的下标处+1即可。(为此,把序列按val排序)
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; pair<int, int> a[N]; #define val first #define pos second struct query { int l, r, x, pos, ans; } q[N]; int n, m; struct BIT { int t[N]; BIT() { memset(t, 0, sizeof(t)); } void add(int i, int x) { for (; i <= n; i += i & -i) t[i] += x; } int sum(int i) { int res = 0; for (; i; i -= i & -i) res += t[i]; return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i].val; a[i].pos = i; } for (int i = 1; i <= m; i++) { cin >> q[i].l >> q[i].r >> q[i].x; q[i].pos = i; q[i].ans = 0; } sort(a + 1, a + 1 + n); sort(q + 1, q + 1 + m, [&](query a, query b) { return a.x < b.x; }); BIT T; int p = 0; for (int i = 1; i <= m; i++) { query& Q = q[i]; while (a[p + 1].val <= Q.x && p + 1 <= n) { p++; T.add(a[p].pos, 1); } Q.ans = T.sum(Q.r) - T.sum(Q.l - 1); } sort(q + 1, q + 1 + m, [&](query a, query b) { return a.pos < b.pos; }); for (int i = 1; i <= m; i++) cout << q[i].ans << "\n"; return 0; }
这篇关于【算法模板】离线树状数组(区间查询小于等于x的数个数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 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有没有大佬知道这种数据应该怎么抓取呀?