首页 > 代码库 > 利用id来进行树状数组,而不是离散化以后的val HDU 4417 离线+树状数组
利用id来进行树状数组,而不是离散化以后的val HDU 4417 离线+树状数组
题目大意:给你一个长度为n的数组,问[L,R]之间<=val的个数
思路:就像标题说的那样就行了。树状数组不一定是离散化以后的区间,而可以是id
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se secondconst int maxn = 1e5 + 5;int tree[maxn], ans[maxn];int n, m;pair<int, int> a[maxn];///val pospair<pair<int, int>, pair<int, int> > b[maxn];///val pos [l,r]int lowbit(int x){return x & -x;}void update(int x){ for (int i = x; i <= n; i += lowbit(i)) tree[i] += 1;}int sum(int x){ int ans = 0; for (int i = x; i > 0; i -= lowbit(i)){ ans += tree[i]; } return ans;}int main(){ int kase = 0; int t; cin >> t; while (t--){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++){ scanf("%d", &a[i].first); a[i].second = i; } sort(a + 1, a + 1 + n); for (int i = 1; i <= m; i++){ int l, r, val; scanf("%d%d%d", &l, &r, &val); l++, r++; b[i] = mk(mk(val, i), mk(l, r)); } sort(b + 1, b + 1 + m); memset(tree, 0, sizeof(tree)); printf("Case %d:\n", ++kase); int j = 1; for (int i = 1; i <= n && j <= m; ){ while (i <= n && b[j].first.first >= a[i].first){ update(a[i].second); i++; } while (j <= m && b[j].first.first < a[i].first){ ans[b[j].first.second] = sum(b[j].second.second) - sum(b[j].second.first - 1); j++; } } while (j <= m){ ans[b[j].first.second] = sum(b[j].second.second) - sum(b[j].second.first - 1); j++; } for (int i = 1; i <= m; i++) { printf("%d\n", ans[i]); } } return 0;}
利用id来进行树状数组,而不是离散化以后的val HDU 4417 离线+树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。