区间求不重复值的和（树状数组求解）

柔情只为你懂 2024-04-19 14:46 64阅读 0赞

#### **题目：**[Galahad][] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA1NDM5Nw_size_16_color_FFFFFF_t_70]

输入
    5 3
    1 3 3 2 1
    1 5
    1 3
    2 4
    
    输出
    6
    4
    5

##### **解题思路：** #####

关键是要先把询问的几个区间先存起来，将其按照区间的右端点从小到大排序，这样当去掉某一区间内的重复值时就不会影响其他区间，因为其他区间的右端点要么比它小，要么比它大，比它小的不会受影响（因为树状数组向上更新），比他大的恰好也要去重。去重时就利用map。

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const ll N = 5e5 + 10;
    ll a[N], b[N], ans[N];
    ll n,m; 
    
    struct node{ 
    
        ll R, L, id;
        friend bool operator < (const node &a, const node &b ){ 
            if(a.R == b.R) return a.L < b.L;
            else return a.R < b.R;
        }
    }tree[N];
    
    ll lowbit ( ll x ) { 
        return x&(-x);
    }
    
    void add ( ll id, ll c ) { 
    
        while(id <= N) { 
            a[id] += c;
            id += lowbit(id);
        }
    }
    
    ll sum ( ll id ) { 
    
        ll sum = 0;
        while(id > 0) { 
            sum += a[id];
            id -= lowbit(id);
        }
        return sum;
    }
    
    int main() { 
    
        scanf("%lld%lld", &n, &m);
        for(int i=1; i<=n; i++) scanf("%lld",&b[i]);
        for(int i=0; i<m; i++) { 
            scanf("%lld%lld",&tree[i].L, &tree[i].R);
            tree[i].id = i;
        }
        sort( tree, tree+m );
        map <ll, ll> mp;
        memset(a, 0, sizeof(a));
        int k = 1;
        for(int i=0; i<m; i++) { 
    
            while(k <= tree[i].R) { 
                ll x = b[k];
                if(mp[x]) add(mp[x], -x);
                add(k, x);
                mp[x] = k++;
            }
            ans[tree[i].id] = sum(tree[i].R) - sum(tree[i].L-1); //注意
        }
        for(int i=0; i<m; i++)
            printf("%lld\n",ans[i]);
    
        return 0;
    }

##### **注意：** #####

上面代码注意处，每个区间不重复和的求解必须在更新完这个区间右端点后就要求解出来，如果到最后在一次性求解，会由于后续区间出现的重复值x，而与此同时 x 假如也存在在这个区间，会导致更新重复值 x 后此区间的值 x也不被计算入此区间的不重复值之和。

[Galahad]: https://ac.nowcoder.com/acm/contest/1084/B
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA1NDM5Nw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a5706a7162c8412590f3803eab943667.png