题目大意

给你一个长度为\(n\)的序列，有\(m\)个询问，每个询问查询区间\([l,r]\)中不同的数的个数。
\(n\leq 50000,m\leq 200000,0\leq a_i \leq 1000000\)

分析

这题显然可以莫队过但是这样AC实在是太没意思了。

考虑用主席树做这题：对于每个前缀\(i\)，我们在前缀\(i-1\)的基础上，将位置\(i\)权值\(+1\)，记\(las[a_i]\)表示权值\(a_i\)上次出现的位置，将位置\(las[{a_i}]\)权值\(-1\)，用这种方法求出所有前缀对应的线段树。

这时若要查询区间\([l,r]\)，我们只需查询前缀\(r\)对应的线段树上，\([l,r]\)的权值和即可。

为什么是对的？考虑一个位置\(i\)，若其满足下面两个条件：

• \(l \leq i \leq r\)中
• \(a_i\)在\([l,r]\)中最后一次出现（等价于\(a_i\)在\([1,r]\)中最后一次出现）

可以发现满足上述条件的一个位置，就代表了一种权值，因此满足条件的位置个数就是答案了。

根据上文方法构造线段树，就能保证前缀\(r\)所对应的线段树中，满足条件的位置值为\(1\)，不满足条件的位置值为\(0\)，因此查询\([l,r]\)的和就是答案。至此问题解决，时空复杂度都是\(O(nloga_i)\)。（比莫队慢？？？）

Code

很久以前写的代码，有点丑，见谅。

#include <cstdio>
#include <cstring>

const int N = 50007, W = 1000007;

int n, q, l, r, tot = 0;

int las[W], root[N], a[N];

struct Tree
{
    int lson[N << 5], rson[N << 5], sum[N << 5];

    void insert(int &rt, int fa, int l, int r, int po, int val)
    {
        if (!rt)
            rt = ++tot;
        sum[rt] = sum[fa] + val;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        if (po <= mid)
            rson[rt] = rson[fa], insert(lson[rt], lson[fa], l, mid, po, val);
        else
            lson[rt] = lson[fa], insert(rson[rt], rson[fa], mid + 1, r, po, val);
    }

    int qrysum(int rt, int l, int r, int ql, int qr)
    {
        if (ql <= l && qr >= r)
            return sum[rt];
        int mid = (l + r) >> 1, ret = 0;
        if (ql <= mid)
            ret += qrysum(lson[rt], l, mid, ql, qr);
        if (mid + 1 <= qr)
            ret += qrysum(rson[rt], mid + 1, r, ql, qr);
        return ret;
    }
} tree;

inline int read()
{
    int x = 0, f = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
    return f ? -x : x;
}

void init()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        *(a + i) = read();
        if (!las[a[i]])
            tree.insert(root[i], root[i - 1], 1, n, i, 1);
        else
        {
            tree.insert(root[i], root[i - 1], 1, n, las[a[i]], -1);
            tree.insert(root[i], root[i], 1, n, i, 1);
        }
        las[a[i]] = i;
    }
}

void solve()
{
    q = read();
    while (q--)
    {
        l = read(), r = read();
        printf("%d\n", tree.qrysum(root[r], 1, n, l, r));
    }
}

int main()
{
    init();
    solve();
    return 0;
}

【SDOI2009】【BZOJ1878】HH的项链

原文：https://www.cnblogs.com/zjlcnblogs/p/11178512.html