HDU 3333 Turing Tree（莫队+离散化）

题意：

给你一个数列，每次询问一个子区间中不同数字的和

思路：

http://blog.csdn.net/roll_keyboard/article/details/78380548
↑和这个题有点像，用莫队即可，在移动区间的时候，发现某个数字是1或者0的时候判断并且更新答案即可，但是直接莫队的复杂度是$O(n\sqrt{n}\log n)$会TLE，要提前离散一下，记录下每个数值的编号，就能把复杂度降为$O(n\sqrt{n})$了

错误及反思：

找了半天bug才发现开始的l,r写反了。。

代码：

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int N=30010;
int arr[N],n,m;
int op[N],num[N];
map<int ,int > mp;
int pos[N];
struct Q
{int l,r,id;
}qu[100010];
long long ans[100010];
long long now;
bool cmp(Q a,Q b)
{if(pos[a.l]!=pos[b.l])return a.l<b.l;return a.r<b.r;
}
void change(int p,int v)
{if(v==-1){if(num[op[p]]==1)now-=arr[p];num[op[p]]--;}else{if(num[op[p]]==0)now+=arr[p];num[op[p]]++;}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);memset(num,0,sizeof(num));int blocks=(int)sqrt(n);int cal=1;for(int i=1;i<=n;i++){scanf("%d",&arr[i]);pos[i]=i/blocks;if(mp[arr[i]]==0) mp[arr[i]]=op[i]=cal++;else op[i]=mp[arr[i]];}scanf("%d",&m);for(int i=0;i<m;i++){scanf("%d%d",&qu[i].l,&qu[i].r);qu[i].id=i;}sort(qu,qu+m,cmp);int l=0,r=-1;now=0;for(int i=0;i<m;i++){while(l<qu[i].l) change(l++,-1);while(l>qu[i].l) change(--l,1);while(r<qu[i].r) change(++r,1);while(r>qu[i].r) change(r--,-1);ans[qu[i].id]=now;}for(int i=0;i<m;i++)printf("%lld\n",ans[i]);mp.clear();}
}