莫队算法（简）

问题：
牛客-Different Integers

https://ac.nowcoder.com/acm/contest/20322/J

给你一个序列a，a1~an，然后q组询问，（l，r），请你算出a1–ai 和 aj—an两个区间的不同的数字个数。
思路：
想简单了，以为是两个区间中不同的数字个数之和，直接前缀和来了一发，果然wa了。它是求前面中不同数字个数和后面中不同的数字个数，就可能这个数字第一次出现的位置不在这两个序列中，但是第二次出现的位置在这两个序列中。
学了学，这是个裸的莫队问题。

莫队问题主要解决多个区间询问的离线算法，很像双指针暴力 ，但是他是一个双指针+分块的算法，复杂度为O(N∗sqrt(N))。
我们先进行分块排序，这样的话，按sqrt（N）的长度分块，左右端点在一个块内的我们按照右端点升序排序，不在一个块的我们按照左端点块的升序排列。
然后l和r的定位要看题目要求，比如这道题就是前面序列和后面序列，所以l=0，r=n+1，有的题l=0，r=n+1，是题目而定。
然后l和r指针的遍历，4个while，
如果 l<询问l，我们往前进，答案数量增加，
如果 r>询问，我们往后推，答案数量增加，
加的那一位进insert。
如果 l>询问l，我们往后退，答案数量减少，
如果r<询问r，我们往前进，答案数量减少，
当前为得减的进remove。
insert函数：
记录数字个数增加数量，如果当前满足题意条件，就答案++
remove函数：
记录数字个数减少数量，如果当前满足题意条件，就答案–
代码

#include
using namespace std;
typedef long long ll;
typedef pairpii;
const int N=1e5+7;
int cnt[N],a[N];
int ans[N],pos[N];
int sum=0;
struct node
{
    int l,r;
    int idx;//存询问的左右区间
} mp[N];
bool cmp(node a,node b)//排序函数（1）
{
    if(pos[a.l]!=pos[b.l])
    {
        return pos[a.l]mp[i].l) rremove(a[l--]);
           
            while(rmp[i].r) iinsert(a[--r]);

            ans[mp[i].idx]=sum;//记录答案

        }
        for(int i=1; i<=q; i++)
        {
           printf("%dn",ans[i]);
        }
    }
    return 0;
}