BZOJ 1878 HH的项链 解题报告

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec  Memory Limit: 64 MB

Description

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

Input

第一行：一个整数N，表示项链的长度。 

第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 

第三行：一个整数M，表示HH询问的个数。 

接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

N ≤ 50000，M ≤ 200000。

Output

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

Sample Input

6

1 2 3 4 3 5

3

1 2

3 5

2 6

Sample Output

2

2

4

Solution

       这是一个染色问题。在正式解决本题前，我们先回忆染色问题的常见类型：

1、  询问动态区间颜色的种类数。
这类问题的颜色的数量很少，一般不超过64种。考虑线段树，每个节点采用状态压缩维护对应区间内的所有颜色。合并两个区间时采用按位或运算即可。

2、  询问静态/动态区间颜色块的数量。
这类问题的颜色的数量通常很多。所谓“颜色块”，就是将连续的具有相同颜色的区间看作一个“块”。同样考虑线段树，每个节点维护对应内颜色块的数量、左端点的颜色、右端点的颜色。合并两个区间时根据左右端点的颜色是否相同分类讨论即可。

3、  询问静态区间颜色的种类数。
与类型1不同，此类问题的颜色数量很多，以至于无法使用状态压缩。假如使用线段树，合并区间时难以有效地去重。注意到一个区间内颜色的种类数等于区间的长度减去区间内重复出现的颜色的出现次数。我们可以假想在两个具有相同颜色的点之间连接一条线段，这样重复出现的颜色的出现次数等于区间内完整的线段的数量。由于统计区间内完整的线段的数量需要使用离线算法，整个过程要求区间为静态。

4、  询问动态区间颜色的种类数。
颜色数量很多，初始时只有一种颜色，修改是将区间染成某种颜色，数据随机生成。我们不得不采用线段树，每个节点$a$维护一个值$c$，设其左右子节点分别为$b_1$、$b_2$，$a.c=\left\{\begin{array}{l}-1,\;b_1.c\neq b_2.c\\b_1.c,\;b_1.c=b_2.c\end{array}\right.$。询问时若遇到$a.c=-1$就继续递归左右子节点。这种做法的查询可能退化，因此需要不断地区间染色防止退化，只有在数据随机生成的前提下才可被采用。

显然，本题属于第3类染色问题。

       我们首先构建线段，维护一个映射lastfind表示一种颜色上一次出现的位置；从左往右扫描整个区间，对于每一个位置i：若color[i]不是首次出现，则添加一条从lastfind[color[i]]到i的线段；然后令lastfind[color[i]]=i。由于颜色种类非常多，映射用std::map维护。实现如下：

for (int i = 1; i <= n; i++)

{

    if (lastfind.count(color[i]) != 0)

    {

        segment[nsegment].left = lastfind[color[i]];

        segment[nsegment].right = i;

        nsegment++;

    }

    lastfind[color[i]] = i;

}

       之后我们思考如何判断一个区间内有多少完整的线段。设$\{a_n\}$和$\{b_n\}$分别是线段左右端点组成的数组。显然线段$\lbrack a_i,b_i\rbrack$完全位于区间$\lbrack l,r\rbrack$的充要条件是$l\leqslant a_i\wedge b_i\leqslant r$。假如我们已知所有的线段的右端点$b_i$都位于区间右端点$r$的左侧，即，$max\{b_n\}\leqslant r$；完全位于区间$\lbrack l,r\rbrack$的线段数量就等于区间$\lbrack l,r\rbrack$内线段左端点$a_i$的数量，即，$\sum_{a_i\in\lbrack l,r\rbrack}1$。至此，我们成功将线段数量转换成了线段左端点的数量。

       为了保证$max\{b_n\}\leqslant r$，我们把询问的区间和线段都按右端点排序。处理询问时，我们引入sum数组，$sum_i$表示以i为左端点的线段的数量。每处理一个新的询问，都更新sum数组，具体来说，如果$b_i\leqslant r$令$sum_{a_i}++$。该询问的结果便等于$r-l+1-\sum_{i=l}^rsum_i$。为了高效地处理询问，可以用树状数组维护sum数组。实现（add和getsum是树状数组的操作）：

sort(segment, segment + nsegment);

sort(query, query + m);

int pinsegment = 0;

for (int i = 0; i<m; i++)

{

    while (segment[pinsegment].right <= query[i].right&&pinsegment<nsegment)

    {

        add(segment[pinsegment++].left);

    }

    query[i].ans = query[i].right - query[i].left + 1 - getsum(query[i].left, query[i].right);

}

       处理完所有询问后，我们需要将询问按输入时的顺序重新排序，然后输出。

       解决区间问题有两种基本方法：

1、  使用线段树，难点是设计将懒标记下传的pushdown函数。

2、  将询问按右端点排序，离线处理。

Code

//两个相同的颜色作为线段的左右端点，将线段按右端点排序

//将询问按右端点排序

//对于每个询问，若右端点右移，则将新包含的区间的左端点加入树状数组

//ans=(query.right-query.left+1)-sum(query.left->query.right)

//其中，query.left、query.right表示询问的左右端点

//sum表示线段左端点是数量

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <map>

#define lowbit(x) ((x)&(-(x)))

using namespace std;

inline void read(int &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

inline void read(long long &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

struct segment_t

{

    bool operator<(const segment_t &b)const

    {

        return right<b.right;

    }

    int left, right;

}segment[50001];

struct query_t

{

    bool operator<(const query_t &b)const

    {

        return right<b.right;

    }

    //询问的左右端点

    int left, right;

    //询问输入的顺序

    int order;

    //询问的答案

    int ans;

}query[200000];

struct cmp

{

    bool operator()(const query_t &a, const query_t &b)const

    {

        return a.order<b.order;

    }

};

map <int, int> lastfind;

int color[50001];

int nsegment = 0;

//树状数组

int tree[50001];

//单点加一

void add(int p)

{

    for (int i = p; i <= 50000; i += lowbit(i))

    {

        tree[i]++;

    }

}

//查询区间和

int getsum(int l, int r)

{

    int ans = 0;

    for (int i = r; i; i -= lowbit(i))

    {

        ans += tree[i];

    }

    for (int i = l - 1; i; i -= lowbit(i))

    {

        ans -= tree[i];

    }

    return ans;

}

int main()

{

    int n, m;

    read(n);

    for (int i = 1; i <= n; i++)

    {

        read(color[i]);

    }

    read(m);

    for (int i = 0; i<m; i++)

    {

        read(query[i].left);

        read(query[i].right);

        query[i].order = i;

    }

    //生成线段

    for (int i = 1; i <= n; i++)

    {

        if (lastfind.count(color[i]) != 0)

        {

            segment[nsegment].left = lastfind[color[i]];

            segment[nsegment].right = i;

            nsegment++;

        }

        lastfind[color[i]] = i;

    }

    sort(segment, segment + nsegment);

    sort(query, query + m);

    int pinsegment = 0;

    //处理询问

    for (int i = 0; i<m; i++)

    {

        while (segment[pinsegment].right <= query[i].right&&pinsegment<nsegment)

        {

            add(segment[pinsegment++].left);

        }

        query[i].ans = query[i].right - query[i].left + 1 - getsum(query[i].left, query[i].right);

    }

    //将询问按输入顺序排序

    sort(query, query + m, cmp());

    for (int i = 0; i<m; i++)

    {

        printf("%d\n", query[i].ans);

    }

    return 0;

}