牛客网暑期ACM多校训练营（第一场）：J-Different Integers（分开区间不同数+树状数组）

链接：J-Different Integers

题意：给出序列a₁, a₂, ..., a_n和区间(l₁, r₁), (l₂, r₂), ..., (l_q, r_q)，对每个区间求集合{a₁, a₂, ..., a_i, a_j, a_{j + 1}, ..., a_n}中不同的数的个数。

题解：

法一：将序列数组在后面复制一遍，就形成了一个环了。这就相当于求连续区间的不同数了。

法二：离线+树状数组

　　　处理出每个数第一次出现的位置first、最后一次出现的位置last和所有的数的种类数tot。将区间(l, r)根据r从小到大排序。从1-n遍历离线数组，如果发现某个数a[i]最后一次出现的位置等于当前i（last[a[i]] == i），就将a[i]第一次出现的位置在树状数组中标记（add(first[a[i]])），当发现r == i时，就保存答案（tot - (sum(maxn - 1) - sum(p[k].l))）。

　　　原理：求出中间丢失的种类数，用总数减去即是答案。当first[a[i]] > l && last[a[i]] < r时，a[i]就不在所求集合里出现。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

int n, q;

int a[maxn];

int bit[maxn];

struct Node{

    int l, r, id;

    bool operator < (const Node& A) const

    {

        return r < A.r;

    }

}p[maxn];

int first[maxn], last[maxn];

int ans[maxn];

void add(int i)

{

    while(i >  && i < maxn){

        bit[i]++;

        i += i & -i;

    }

}

int sum(int i)

{

    int ans = ;

    while(i){

        ans += bit[i];

        i -= i & -i;

    }

    return ans;

}

int main()

{

    while(scanf("%d%d", &n, &q) != EOF){

        memset(bit, , sizeof(bit));

        memset(first, -, sizeof(first));

        memset(last, -, sizeof(last));

        int tot = ;

        for(int i = ; i <= n; i++){

            scanf("%d", &a[i]);

            last[a[i]] = i;

            if(first[a[i]] == -){

                tot++;

                first[a[i]] = i;

            }

        }

        for(int i = ; i < q; i++){

            scanf("%d%d", &p[i].l, &p[i].r);

            p[i].id = i;

        }

        sort(p, p + q);

        memset(ans, , sizeof(ans));

        for(int i = , k = ; i <= n; i++){

            while(k < q && p[k].r == i){

                ans[p[k].id] = tot - (sum(maxn - ) - sum(p[k].l));

                k++;

            }

            if(last[a[i]] == i){

                add(first[a[i]]);

            }

        }

        for(int i = ; i < q; i++) printf("%d\n", ans[i]);

    }

}

牛客网暑期ACM多校训练营（第一场）：J-Different Integers（分开区间不同数+树状数组）的相关教程结束。