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

梦里梦外; 2021-12-22 16:37 185阅读 0赞

题目大意：给你一个长度为n的数组，问\[L,R\]之间<=val的个数

思路：就像标题说的那样就行了。树状数组不一定是离散化以后的区间，而可以是id

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//看看会不会爆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 second
    const int maxn = 1e5 + 5;
    int tree[maxn], ans[maxn];
    int n, m;
    pair<int, int> a[maxn];///val pos
    pair<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;
    }

转载于:https://www.cnblogs.com/heimao5027/p/5870059.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/18a29888ad384766b3c0d52f427cb024.png