【题解】P1972 [SDOI2009]HH的项链 - 树状数组

2024-02-02 18:13:22

P1972 [SDOI2009]HH的项链

声明：本博客所有题解都参照了网络资料或其他博客，仅为博主想加深理解而写，如有疑问欢迎与博主讨论✧｡٩(ˊᗜˋ)و✧*｡

题目描述

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

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

输入格式

一行一个正整数 \(n\) ，表示项链长度。

第二行 \(n\) 个正整数 \(a_i\) ，表示项链中第 \(i\) 个贝壳的种类。

第三行一个整数 \(m\)，表示 \(H\) 询问的个数。

接下来 \(m\) 行，每行两个整数 \(l,r\) 表示询问的区间。

输出格式

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

Solution

首先贴一下我觉得写得非常清楚的题解，以下转载自这篇题解：

"这个题用树状数组，线段树等等都可以做，不过用树状数组写起来更方便。

此题首先应考虑到这样一个结论：

对于若干个询问的区间 \([l,r]\)，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的，例如：

项链是：\(1 \ 3 \ 4 \ 5 \ 1\)

那么，对于 \(r=5\) 的所有的询问来说，第一个位置上的 \(1\) 完全没有意义，因为 \(r\) 已经在第五个 \(1\) 的右边，对于任何查询的 \([L,5]\) 区间来说，如果第一个 \(1\) 被算了，那么他完全可以用第五个 \(1\) 来替代。

因此，我们可以对所有查询的区间按照 \(r\) 来排序，然后再来维护一个树状数组，这个树状数组是用来干什么的呢？看下面的例子：

\(1 \ 2 \ 1 \ 3\)

对于第一个 \(1\)，\(insert(1,1)\)；表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是：\(1 \ 0 \ 0 \ 0\)

对于第二个 \(2\)，\(insert(2,1)\)；此时树状数组表示的每个数字是 \(1 \ 1 \ 0 \ 0\)

对于第三个 \(1\)，因为之前出现过 \(1\) 了，因此首先把那个 \(1\) 所在的位置删掉 \(insert(1,-1)\),然后在把它加进来 \(insert(3,1)\) 。此时每个数字是\(0 \ 1 \ 1 \ 0\)

如果此时有一个询问 \([2,3]\)，那么直接求 \(sum(3)-sum(2-1)=2\)就是答案。

题解清楚么？"

看完之后觉得，哇，这道题也就这样嘛，不难啊。可是为什么我接触树状数组一个多学期了，这样基础的题目都想不到，运用不好呢？

一个数据结构，最重要的就是运用，于是借这道题简单理顺一下树状数组。

树状数组支持以下：

\(1.\) 单点修改
\(2.\) 区间修改（维护差分）
\(3.\) 单点查询
\(4.\) 前缀查询
\(5.\) 区间查询（实际上是前缀的运用）

所以，碰到一道数据结构的题，若它可以通过发现本题的某些特殊性质，进而转化为和 前缀和、区间和 有关的问题，那么就可以尝试用树状数组做。

例如这道题，经过观察后（\(ps:\) 这个观察往往也是非常非常重要的，一般来说可以多手算几组合适的样例）发现区间的变动非常不好处理，那么我们就把 \(r\) 相等的区间分为一组来考虑，再排序，进一步发现种类数只和最靠近 \(r\) 的有关，从而转化为一个动态求区间值的问题。

Code

#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define lowbit(x) x & -x
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read(); 
const int N = 1e6 + 5;
int n, q;
int a[N];
int tree[N];
int last[N];
struct node{
    int l, r, num, ans;
}k[N]; 
bool cmp1(node x, node y){ return x.r < y.r;}
bool cmp2(node x, node y){ return x.num < y.num;}
void add(int pos, int v)
{
    for(; pos <= n; pos += lowbit(pos)) tree[pos] += v;
}
int getsum(int pos)
{
    int res = 0;
    for(; pos; pos -= lowbit(pos)) res += tree[pos];
    return res;
}
int main()
{
    n = read();
    F(i, 1, n) a[i] = read();
    q = read();
    F(i, 1, q) k[i].l = read(), k[i].r = read(), k[i].num = i;
    sort(k + 1, k + 1 + q, cmp1);
    F(i, 1, q)
    {
        if(k[i].r != k[i - 1].r)
            F(j, k[i - 1].r + 1, k[i].r)
            {
                if(last[a[j]]) add(last[a[j]], -1);
                add(j, 1), last[a[j]] = j;
            }
        k[i].ans = getsum(k[i].r) - getsum(k[i].l - 1);
    }
    sort(k + 1, k + 1 + q, cmp2);
    F(i, 1, q) printf("%d\n", k[i].ans);
    return 0;
}
int read()
{
    int x = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

码农公寓