首页 > 代码库 > 利用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;}
View Code

 

利用id来进行树状数组,而不是离散化以后的val HDU 4417 离线+树状数组