F (莫队+分块)little w and Discretization

首先啊，我们可以知道，对于数值大于 3e5 的数，离散化后一定会变得不同。所以将其变为3e5+1既可。
经过观察我们发现本题和mex有关（最小未出现正整数）。求出mex后对于大于mex的数，一定是会变得不同的。
举个例子， [1,2,4,7] 的mex为3 离散后的结果为[1,2,3,4] 大于3 的数都变得不同了。

那么怎么求mex

贴个链接
https://www.luogu.com.cn/problem/P4137
(这里的mex是最小的未出现的非负整数，也就是说可以是0)
我们发现题解里有很多说主席树的，但是我们不会怎么办（但是题解里有说莫队的被我看到了）
如果你打过杭电多校，那么你一定记得有个题是莫队套分块的。
求mex也是这样的，这里就关放上add del que的代码

inline void add(int p)
{
    cot[p]++;
    if (cot[p] == 1)sum[p / sq]++;
}
inline void del(int p)
{
    cot[p]--;
    if (cot[p] == 0)sum[p / sq]--;
}

inline int que() {
    for (int i = 1; i <= sq; i++) {
        if (sum[i - 1] != sq) {
            for (int j = (i - 1)*sq; j < i*sq; j++) {
                if (!cot[j])return j;
            }
        }
    }
}

需要解释的就是que了，sum保存着每个块中的出现的数的个数，如果不等于sq，说明没有放满，第一个没有放满的块里就有我们要的mex。

是不是很简单，然后就在分块套一个区间求和既可
注意由于本题只要正整数，所以mex不能是0，第一个块的大小应该是sq-1，特判一下就可以了。

const int maxnum = 3e5 + 5;

int sq = 550;
int sum[550];//求mex的
int cot[maxnum];//求mex的

int cnt[maxnum];//求和的
int S[maxnum];//求和的
int SUM;//求和的
struct query // 把询问以结构体方式保存
{
    int l, r, id;
} Q[maxnum];

bool cmp(query &a, query &b) {
    if (a.l / sq != b.l / sq)
        return a.l < b.l;
    if ((a.l / sq) & 1)
        return a.r < b.r;
    return a.r > b.r;
}
int ans[maxnum];
int a[maxnum];
int n, m;
inline void add(int p)
{
    cot[p]++;
    if (cot[p] == 1)sum[p / sq]++;

    cnt[p]++;
    S[p / sq]++;
    SUM++;
}
inline void del(int p)
{
    cot[p]--;
    if (cot[p] == 0)sum[p / sq]--;

    cnt[p]--;
    S[p / sq]--;
    SUM--;
}

inline int pre(int p) {
    int res = 0;
    for (int i = 0; i < p / sq; i++) res += S[i];
    for (int i = p / sq * sq; i <= p; i++)res += cnt[i];
    return res;
}



inline int que() {
    for (int i = 1; i <= sq; i++) {
        if ((i - 1) == 0) {
            if (sum[i - 1] != sq - 1) {
                for (int j = (i - 1)*sq + 1; j < i*sq; j++) {
                    if (!cot[j])return j;
                }
            }
        }
        else {
            if (sum[i - 1] != sq) {
                for (int j = (i - 1)*sq; j < i*sq; j++) {
                    if (!cot[j])return j;
                }
            }
        }

    }
}

void slove() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] > 3e5)a[i] = 3e5 + 1;
    }
    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 l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        while (l > Q[i].l)
            add(a[--l]);
        while (r < Q[i].r)
            add(a[++r]);
        while (l < Q[i].l)
            del(a[l++]);
        while (r > Q[i].r)
            del(a[r--]);
        int mex = que();
        ans[Q[i].id] = SUM - pre(mex);
    }
    for (int i = 1; i <= m; i++)cout << ans[i] << endl;
}

完整代码地址
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48813168