题意
题目链接：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;
}