HH的项链(莫队/树状数组/主席树)

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式
一行一个正整数 n，表示项链长度。
第二行 n 个正整数 ai，表示项链中第 i 个贝壳的种类。

第三行一个整数 m，表示 H 询问的个数。
接下来 m 行，每行两个整数 l,r，表示询问的区间。

输出格式
输出 m 行，每行一个整数，依次表示询问对应的答案。

输入输出样例
输入 #1复制
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出 #1复制
2
2
4

题解（莫队）

首先考虑莫队算法，离线操作，先对询问的l进行从小到大排序，相同的r如果在相同的块内，按照从小到大排序
莫队是一种离线暴力算法，采用的分块的思想，将询问的区间按照左端点和相同块内的右端点，从小到大排序，再用类似于双指针的操作，去左移右移区间来查询
代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
#define gcd __gcd
#define endl 'n'
#define mem(x, y) memset(x, y, sizeof(x))
#define inf 0x3f3f3f
#define ninf 0xc0c0c0c0
#define y second
#define x first
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef pair PII;
const int M = 200010, N = 50010;
int t, len;
int a[N], cnt[(M * 10 << 1)], ans[M << 1];
int get(int i)
{
    return i / len;
}
struct node
{
    int l, r, i;
    bool operator<(const node &t) const
    {
        int a = get(l), b = get(t.l);
        if (a != b)
            return a < b;
        return r < t.r;
    }
} q[M << 1];

void add(int i, int &res)
{
    cnt[i]++;
    if (cnt[i] == 1)
        res++;
}
void del(int i, int &res)
{
    cnt[i]--;
    if (cnt[i] == 0)
        res--;
}
void solve()
{
    int n, m;
    cin >> n;
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].i = i;
    }
    sort(q + 1, q + m + 1);
    int res = 0, i = 0, j = 1;
    for (int k = 1; k <= m; k++)
    {
        int id = q[k].i, l = q[k].l, r = q[k].r;
        while (i < r) add(a[++i], res);
        while (i > r) del(a[i--], res);
        while (j < l) del(a[j++], res);
        while (j > l) add(a[--j], res);
        ans[id] = res;
    }
    for (int i = 1; i <= m; i++)
    {
        cout << ans[i] << "n";
    }
}
signed main()
{
    FAST;
    solve();
}

题解（树状数组）

用树状数组的思想和莫队差不多，都是离线暴力，但是树状数组的时间复杂度更加优秀，首先把所有的询问储存进来，按找右端点从小到大进行排序后；
先不把值存进树状数组里，我们先定义一个pos，作为树状数组的下标，代表我们已经维护到了pos的位置，每次查询都更新到询问的r值，定义一个标记数组存每个数字最后一次出现的下标，每次先加上现在这个值的贡献，如果之前已经存在这个值了，再把这个值的贡献减掉，更新标记数组的值

#include 
#define ll long long
#define gcd __gcd
#define endl 'n'
#define mem(x, y) memset(x, y, sizeof(x))
#define inf 0x3f3f3f
#define ninf 0xc0c0c0c0
#define se second
#define fr first
using namespace std;
typedef pair PII;
const int N = 1000010;
int a[N];
int c[N];
int n, m;
struct node
{
    int l, r, id;
    bool operator<(const node &t) const
    {
        if (r == t.r)
            return l < t.l;
        else
            return r < t.r;
    }
} q[N];
int lowbit(int x) { return x & -x; }

void add(int i, int x)
{
    for (; i <= n; i += lowbit(i))
        c[i] += x;
}
int ask(int i)
{
    int sum = 0;
    for (; i > 0; i -= lowbit(i))
        sum += c[i];
    return sum;
}

map p;
int ans[N];
void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        int l, r, id;
        scanf("%d%d", &l, &r);
        q[i] = {l, r, i};
    }
    sort(q + 1, q + m + 1);
    int pos = 0;
    for (int i = 1; i <= m; i++)
    {
        int l = q[i].l, r = q[i].r, idx = q[i].id;
        while (pos + 1 <= r)
        {
            pos++;
            add(pos, 1);
            if (p[a[pos]])
                add(p[a[pos]], -1);
            p[a[pos]] = pos;
        }
        ans[idx] = ask(r) - ask(l - 1);
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%dn", ans[i]);
    }
}
signed main()
{
    solve();
}

题解（主席树）

后续更新。。。

HH的项链(莫队/树状数组/主席树)

C/C++/C#相关栏目本月热门文章