Different Integers(树状数组求区间内不同数的个数)

题目链接

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

题目大意

给你n个数字和q次查询,每次查询查询1-l加上r-n的这段区间内有多少不同的数。

思路

和以前用主席树时的做法思路一样,也是要先把n个数复制一遍,然后再用树状数组求解。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 1000;
int n, q;
int a[maxn], pre[maxn];
struct node {
    int l, r, ans, id;
} qq[maxn];

bool cmp(node a, node b) {
    return a.id < b.id;
}

bool cmpp(node a, node b) {
    return a.l < b.l;
}

struct BIT {
    int bit[maxn];

    int lowbit(int x) {
        return x & (-x);
    }

    void update(int id, int x) {
        for (int i = id; i <= n + n; i += lowbit(i)) {
            bit[i] += x;
        }
    }

    int query(int q) {
        int ans = 0;
        for (int i = q; i > 0; i -= lowbit(i)) {
            ans += bit[i];
        }
        return ans;
    }

    void init() {
        memset(bit, 0, sizeof(bit));
    }
} bittree;

int main() {
    while (~scanf("%d%d",&n,&q)) {
        memset(pre, 0, sizeof(pre));
        bittree.init();
        for (int i = 1; i <= n; i++) {
            scanf("%d",&a[i]);
            a[i + n] = a[i];
        }
        for (int i = 1; i <= q; i++) {
            scanf("%d%d",&qq[i].l,&qq[i].r);
            qq[i].id = i;
        }
        sort(qq + 1, qq + q + 1, cmpp);
        int p = 1;
        for (int i = 1; i <= n + n && p <= q; i++) {
            bittree.update(i, 1);
            if (pre[a[i]])
                bittree.update(pre[a[i]], -1);
            pre[a[i]] = i;
            while (p <= q && qq[p].l + n == i) {
                qq[p].ans = bittree.query(qq[p].l + n) - bittree.query(qq[p].r - 1);
                p++;
            }
        }
        sort(qq + 1, qq + q + 1, cmp);
        for (int i = 1; i <= q; i++) {
            printf("%d\n",qq[i].ans);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注