本文共 3500 字，大约阅读时间需要 11 分钟。

题意

长度为N的数组，Q次询问，每次询问给两个数 L,R，求区间 [1, L] 和 [R, N]中一共有几种数

AC

• 暴力肯定超时，用树状数组维护
  离线考虑没出现的数字个数假设 r > last[x]，那么当l < first[x] 时，则x 没出现
  有两种实现方式：
  1. 按照查询区间的右端点升序
     当数字最后出现在这个右端点处，那么下面的区间的右侧至少不会出现这个数字，因为下个区间的右端点大于等于上个区间，只用判断左区间就ok
  2. 按照查询区间的左端点降序
     当数字第一次出现在左端点处，那么下一个区间的左侧至少不会出现这个数字，因为下个区间的左端点小于上个区间，只用判断右区间就ok
• 左端点降序

using namespace std;struct ac{    int l, r, id;    bool operator <(const ac &x) {        return l > x.l;    }};int main() {#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int n, q;    while (scanf("%d%d", &n, &q) != EOF) {        // 记录每个数 开始出现的位置 和 最后出现的位置        vector
   
     a(n + 1), first(n + 1), last(n + 1);        // 统计数字种类        int sum = 0;        for (int i = 1; i <= n; ++i) {            scanf("%d", &a[i]);            last[a[i]] = i;            if (!first[a[i]])                first[a[i]] = i, sum++;        }        // queries 存放询问        vector
    
      queries(q);        for (int i = 0; i < q; ++i) {            scanf("%d%d", &queries[i].l, &queries[i].r);            queries[i].id = i;        }        // 按照询问左区间降序        sort(queries.begin(), queries.end());        // count 记录不在范围中的数        // ans 记录每次询问的结果        vector
     
       count(n + 1), ans(q);        for (int i = n, k = 0; i >= 1; --i) {            // 枚举每个区间            while (k < q && queries[k].l == i) {                if (k == q) break;                ans[queries[k].id] = sum;                // 减去不在区间的数字， 向左枚举                for (int j = queries[k].r; j > 0; j -= lowbit(j)) {                    ans[queries[k].id] -= count[j];                }                k++;            }            // 更新不在区间的数字            if (first[a[i]] == i) {                for (int j = last[a[i]] + 1; j <= n; j += lowbit(j)) {                    count[j]++;                }            }        }        for (int i = 0; i < q; ++i) {            printf("%d\n", ans[i]);        }    }    return 0;}
     
    
   

• 右端点升序

using namespace std;struct ac{    int l, r, id;    bool operator <(const ac &a) {        return r < a.r;    }};int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int n, q;    while (~scanf("%d%d", &n, &q)) {        // 记录每个数 开始出现的位置 和 最后出现的位置        vector
   
     a(n + 1), last(n + 1), first(n + 1);        // 统计数字种类        int sum = 0;        for (int i = 1; i <= n; ++i) {            scanf("%d", &a[i]);            last[a[i]] = i;            if (!first[a[i]]) {                first[a[i]] = i;                sum++;            }        }        // count 记录不在范围中的数        // ans 记录每次询问的结果        vector
    
      count(n + 1), ans(q);        // queries 存放询问        vector
     
       queries(q);        for (int i = 0; i < q; ++i) {            scanf("%d%d", &queries[i].l, &queries[i].r);            queries[i].id = i;        }        // 按照询问右端点升序        sort(queries.begin(), queries.end());        int k = 0;        for (int i = 1; i <= n && k < q; ++i) {            while (k < q && queries[k].r == i) {                ans[queries[k].id] = sum;                // 减去不在区间的数字， 向左枚举                for (int j = queries[k].l; j <= queries[k].r; j += lowbit(j)) {                    ans[queries[k].id] -= count[j];                }                ++k;            }            // 更新不在区间的数字            if (last[a[i]] == i) {                for (int j = first[a[i]] - 1; j > 0; j -= lowbit(j)) {                    count[j]++;                }            }        }        for (int i = 0 ; i < q; ++i) {            printf("%d\n", ans[i]);        }    }
     
    
   

转载地址：http://xkprf.baihongyu.com/