计算区间不同数的和（离线+树状数组）

题目传送门:牛客练习赛52-B：Galahad

题意：

给一个长度为n的数组，有q次询问，每次询问一个区间 $[l,r]$[l,r]​ ，问这个区间的和，但如果某一个数在这个区间出现了多次，这个数只能被计算一次。

思路：

题目中只有修改操作，所以我们可以离线处理。

我们让所有查询按右端点从小到大排序。对于每个区间将未添加的原数组元素设为 $w\left[p\right]$w[p]，如果 $w\left[p\right]$w[p] 在前面已经出现过，那就让前面的删除。让p这个位置的值变为 $w\left[p\right]$w[p]。最后对于这个区间求区间合即可。

这样的话区间中出现相同的数只有最后出现位置才有贡献。且有这个数必可以计算出贡献。

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=5e5+20;
const int mod=1e9+7;
int vis[N];
struct Seqment
{
    int l,r,id;
    bool operator < (const Seqment & o) const
    {
         return r<o.r;
    }
} seq[N];
struct TreeArray
{
    int MXN;
    ll bt[N];
    int lowbit(int k)
    {
        return k&-k;
    }
    void modify(int k,ll val)
    {
        while(k<=MXN)
        {
            bt[k]+=val;
            k+=lowbit(k);
        }
    }
    ll getpre(int k)
    {
        ll sum=0;
        while(k)
        {
            sum+=bt[k];
            k-=lowbit(k);
        }
        return sum;
    }
    ll getsum(int l,int r)
    {
        return getpre(r)-getpre(l-1);
    }

}solve;
ll w[N],res[N];
int main()
{
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    scanf("%d%d",&n,&m);
    solve.MXN=n;
    for(int i=1;i<=n;++i){
            scanf("%lld",&w[i]);
// cin>>w[i];
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d",&seq[i].l,&seq[i].r);
        seq[i].id=i;
    }
    sort(seq+1,seq+m+1);
    int p=0;
    for(int i=1;i<=m;++i)
    {
        while(p+1<=seq[i].r){
            ++p;
            if(vis[w[p]]!=0){
                solve.modify(vis[w[p]],-w[p]);
            }
            vis[w[p]]=p;
            solve.modify(p,w[p]);
        }
        res[seq[i].id]=solve.getsum(seq[i].l,seq[i].r);
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",res[i]);
    }
    return 0;
}