HDU 3874-Necklace（线段树+单点修改）

题意

题目链接：Problem - 3874 (hdu.edu.cn)
给你一个长度为$n(1\leq n \leq 50000)$的数组，以及$q(1\leq q\leq 200000)$次询问，每次询问有两个数字$x,y$，询问区间$[x,y]$的漂亮值是多少，漂亮值定义如下：对于区间$[x,y]$内所有不同元素的和，例如区间内有$3,5,5$，那么值就是$3+5=8$。

思路

显然是RMQ问题，但是这个不重复的数字很麻烦，我迅速敲了一个莫队上去，果不其然TLE了，查询次数太多以及还有多组询问，所以需要用到线段树/树状数组的“单点修改，区间查询”

首先得有一个莫队的对询问区间排序的思想，我们按照区间的右边界进行排序，这样我们每次for i=1...n的时候就不需要考虑前面的了，例如我处理完$[1,3]$和$[2,3]$，新进来$4$的时候，跟前面的没有关系。

struct Mo
{
    int l,r,id;
    int ans;
}q[N];
bool cmp(Mo a,Mo b)
{
    return a.r<b.r;
}

重点在这里：
然后就是如何处理这个重复的问题，我因为思想是往右递增的，所以我这颗树不像平时的线段树是一开始全部build好，而是一开始是空树，随着递增一个个进入树，满足条件的退出树。

满足什么样的条件就退出？当x在树中但又进来了一个x,这个时候原来那个x是没有贡献的了，因为无论是计算值（后面代替前面的），还是说后面又有重复的x，都与原来的没有关系了。
例如原来3这个数字在i=2的位置，那个时候第一次出现，加入到树中(optadd(1,2,3))，让树2的位置加3，假如在i=5的时候，又有3出现，所以这个时候需要将原来的删除，删除的话也是用加法——optadd(1,2,-3)即可，然后加入i=5这个时候的3，也就是optadd(1,5,3)即可。

struct Segment_Tree
{
    int sumv[N<<2],lc[N<<2],rc[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
    inline void build(int o,int l,int r)
    {
        lc[o]=l;rc[o]=r;sumv[o]=0;//空树，一开始全为0
        if (l==r) return ;
        build(lson,l,mid);build(rson,mid+1,r);
    }
    inline void optadd(int o,int pos,int val)
    {
        sumv[o] += val;//维护当前值，边往下传边加，单点修改
        int l=lc[o],r=rc[o];
        if (l==r) return;//以及到达需要的结点
        if (pos<=mid) optadd(lson,pos,val);
        else optadd(rson,pos,val);//判断pos的位置，在lson还是rson
    }
    inline int query(int o,int ql,int qr)
    {
        int l = lc[o], r = rc[o];
        if (ql<=l&&r<=qr) return sumv[o];
        int ans=0;
        if (ql<=mid) ans+=query(lson,ql,qr);
        if (qr>mid) ans+=query(rson,ql,qr);
        return ans;
    }//区间查询
}tree;

这样的话，我就一直能保证这颗树里面的值只出现一次，并且是当前最右边的，所以我这样按照区间排序可以一直统计答案，最后对于区间的id进行排序输出即可。

for (int i=1;i<=n;i++)
{
    tree.optadd(1,i,a[i]);//加入树中，单点修改
    if (mp[a[i]]) tree.optadd(1,mp[a[i]],-a[i]);//删除
    mp[a[i]] = i;//统计当前最右边的位置
    while (cur<=m&&q[cur].r==i)//将满足条件的区间都进行统计 q[cur].r==i 右区间已经达到
    {
        q[cur].ans = tree.query(1,q[cur].l,q[cur].r);
        cur++;//处理下一个区间
    }
}

代码

struct Mo
{
    int l,r,id;
    int ans;
}q[N];
bool cmp(Mo a,Mo b)
{
    return a.r<b.r;
}
bool CMP(Mo a,Mo b)
{
    return a.id<b.id;
}
int a[N],n,m;
struct Segment_Tree
{
    int sumv[N<<2],lc[N<<2],rc[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
    inline void build(int o,int l,int r)
    {
        lc[o]=l;rc[o]=r;sumv[o]=0;
        if (l==r) return ;
        build(lson,l,mid);build(rson,mid+1,r);
    }
    inline void optadd(int o,int pos,int val)
    {
        sumv[o] += val;
        int l=lc[o],r=rc[o];
        if (l==r) return;
        if (pos<=mid) optadd(lson,pos,val);
        else optadd(rson,pos,val);
    }
    inline int query(int o,int ql,int qr)
    {
        int l = lc[o], r = rc[o];
        if (ql<=l&&r<=qr) return sumv[o];
        int ans=0;
        if (ql<=mid) ans+=query(lson,ql,qr);
        if (qr>mid) ans+=query(rson,ql,qr);
        return ans;
    }
}tree;
map<int,int> mp;
inline void Case_Test()
{
    cin>>n;
    tree.build(1,1,n);
    mp.clear();
    for (int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for (int i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int cur = 1;
    for (int i=1;i<=n;i++)
    {
        tree.optadd(1,i,a[i]);
        if (mp[a[i]]) tree.optadd(1,mp[a[i]],-a[i]);
        mp[a[i]] = i;
        while (cur<=m&&q[cur].r==i)
        {
            q[cur].ans = tree.query(1,q[cur].l,q[cur].r);
            cur++;
        }
    }
    sort(q+1,q+m+1,CMP);
    for (int i=1;i<=m;i++)
        cout<<q[i].ans<<endl;
}