[SDOI2009]HH的项链题解

发布于 2019-11-06  266 次阅读


离线+树状数组维护

题面

洛谷链接

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入格式

第一行:一个整数N,表示项链的长度。

第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。

第三行:一个整数M,表示HH 询问的个数。

接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式

M 行,每行一个整数,依次表示询问对应的答案。

题解

这题似乎可以用莫队???不过我不会QAQ

思路大致是这样的:

树状数组维护一个前缀和f[i],代表从第一个位置到$i$个位置有多少个不同的数。

于是发现区间不同的值不好维护,我们可以把它离线下来。

我们按询问区间的右端点从小到大排序,之后从第一个数据开始处理。一旦后面的值和前面的值相同,那么在询问包含这个数的区间的时候,后面的值完全可以把前面的值替换掉。

例如

1 2 1 4 3 5

  1. 在第1位插入1(表示第一位有一个不一样的数),标记1
  2. 在第2位插入1,标记2
  3. 在第3位插入1,发现已被标记,于是清除第一位的1
  4. 询问1~3,sum(3) - sum(0)

因为我们询问的区间已按右端点排过序,所以询问的区间不管包不包含已删掉的元素,答案都只被最后一个相同的元素影响。

有点啰嗦了,感性理解一下吧。

代码

#include <bits/stdc++.h>

#define endl '\n'
#define R register
#define lowbit(x) x & -x
using std::cin;
using std::cout;

const int maxn = 1000005;
int a[maxn], b[maxn], n;
int next = 1, vis[maxn], ans[maxn], m;

inline void add(int pos, int x)
{
    for (R int i = pos; i <= n; i += lowbit(i))
        a[i] += x;
}

inline int sum(int pos)
{
    int ans = 0;
    for (R int i = pos; i > 0; i -= lowbit(i))
        ans += a[i];
    return ans;
}

struct ask
{
    int l, r, pos;
    bool operator<(const ask &b) const
    {
        return r < b.r;
    }
} q[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (R int i = 1; i <= n; i++)
        cin >> b[i];

    cin >> m;

    for (R int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].pos = i; //记录这个询问的位置
    }

    std::sort(q + 1, q + m + 1);

    for (R int i = 1; i <= m; i++)
    {
        for (R int j = next; j <= q[i].r; j++)
        {
            if (vis[b[j]])
                add(vis[b[j]], -1);  //打上-1是清零:1 + (-1)=0
            vis[b[j]] = j;
            add(j, 1);
        }
        ans[q[i].pos] = sum(q[i].r) - sum(q[i].l - 1); //离线计算答案
        next =  q[i].r + 1;
    }

    for (R int i = 1; i <= m; i++)
        cout << ans[i] << endl;

    return 0;
}