HH的项链 解题报告

叶小枫 · 2019-11-03 00:48:46 · 题解

HH的项链 解题报告

……（妈耶那我凉了啊），怎么后面还有一句

本题可能需要较快的读入方式，最大数据点读入数据约20MB

噫。那行吧，想一想正解是什么东西。既然是从树状数组板子旁边揪出来的那就是树状数组咯，然而很闲的我又喵到了刚刚打完的线段树板子……线段树……？

翻了一下其他题解，这可能是唯一一篇同时讲解了线段树和树状数组两种常见做法的解题报告，所以就筹划着写下来了。至于其他julao们写的主席树、莫队、离散化、分块……本蒟蒻一个都不会，就不在此班门弄斧了。

核心思想

最大那个点（#10）数据有20MB，这已经不是普通的scanf能承受的了。也许关了流同步的cin可以过，我没有试。所以上手先来一个快读，在此就略过。

读一下题目，我们发现一句话，也就是他的问题：“某一段贝壳中，包含了多少种不同的贝壳？”。这句话里包含了两个意思：1. 询问的是一个区间，2. 对于同一种贝壳，如果在询问的区间中重复出现，那么就可以只关注它出现的某一个位置而忽略其他同类的贝壳。

事实上，这两点也就是这道题目的核心思想。那么接下来要考虑的就是，我们要关注在区间内哪一个位置的同类贝壳。因为在一个区间中除了端点以外，其它中间元素的位置和数目都是不确定的，所以一种思路显而易见：只关注在两端点处出现的同类贝壳。第一篇高赞题解说的也就是这个事情，他选择了右端点作为判断的标准，其实左端点当然也可以（只要反着建树就好了）。但是完全没必要把整个树状数组反过来，所以在此也仅讨论取最右边一个同类贝壳的情况。

既然只关注最右边的贝壳，那么就需要依次从左向右地处理和修改整个数组，这样才能保证我们对于前一个区间的修改不会影响到后面区间的询问。当然还有一点，在关注了最右边贝壳之后，要忽略区间内其他同类的贝壳。

还有一个问题，我们要对区间询问什么东西？这就涉及到前缀和的思想：对于每一个区间，询问在它右端点之前有多少不同类的贝壳。因为由于我们之前的修改操作，所有同类的贝壳已经被简化到只剩最靠右边那个，所以可以保证这种做法的正确性。

所以经过总结，我们可以得到这样的总思路：

1. 我们需要一种支持单点修改、区间查询的数据结构
2. 对给定的询问区间，按照区间右端点进行排序，按排序后的顺序记录答案，然后原序输出。
3. 每个询问区间的答案就是区间右端点的前缀和-(区间左端点-1)的前缀和。

由此我们引出此解题报告的主角：树状数组和线段树。

树状数组解法

思路

单点修改、区间查询前缀和，树状数组真是一个再好不过的选择了。首先当然要开一个结构体存储询问的各个区间，方便排序和原序输出，再写一个cmp：

struct QUE{
    int l;
    int r;
    int id; // 存放原序
}q[maxn];
inline bool cmp(const QUE &a,const QUE &b){
    return a.r<b.r;
}

然后就是树状数组的几个板子，lowbit，modify以及query，在此也不多解释：

inline int lowbit(int x){
    return x&(-x);
}
void modify(int p,int v){
    for(;p<=n;p+=lowbit(p))
        tree[p]+=v;
}
int query(int p){
    int res=0;
    for(;p;p-=lowbit(p))
        res+=tree[p];
    return res;
}
// tree数组即为树状数组

下面引入重要的一个数组vis[]以及一个变量pow。vis[i]表示第i种贝壳在目前询问到的区间中最后出现的位置（也就是最右端）。变量pow指向的位置是尚未修改的区间的左端点，也就是已经修改区间右端点的后一个位置，方便定位未修改的区间。由于我们已经对询问的区间按右端点排好序，所以pow的值在不同时刻单调递增，直至末尾。

有了以上的信息之后就我们可以对区间进行修改了，主要维护两个操作：

1. 如果某元素i在之前已经出现过，那么将其以前最右端位置的前缀和-1，相当于忽略之前的位置。再在现在i的位置把前缀和+1，并更新vis[i]到当前位置。
2. 如果某元素i在之前没有出现，那么直接修改当前位置前缀和即可，并更新vis[i]。

最后再算一下当前询问区间的答案即可，以上两个操作如下：

int pow=1;
    for(rint i=1;i<=m;++i){
        for(rint j=pow;j<=q[i].r;++j){
            if(vis[a[j]]) modify(vis[a[j]],-1);
            modify(j,1);
            vis[a[j]]=j;
        }
        pow=q[i].r+1;
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }

总代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define rint register int
#define maxn 1000010
using namespace std;

int n,m;
int a[maxn],ans[maxn];
int vis[maxn],tree[maxn];

struct QUE{
    int l;
    int r;
    int id;
}q[maxn];

inline void read(int &x){
    char ch=getchar();int f=1;x=0;
    while(!isdigit(ch) && ch^'-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}

inline bool cmp(const QUE &a,const QUE &b){
    return a.r<b.r;
}

inline int lowbit(int x){
    return x&(-x);
}

void modify(int p,int v){
    for(;p<=n;p+=lowbit(p))
        tree[p]+=v;
}

int query(int p){
    int res=0;
    for(;p;p-=lowbit(p))
        res+=tree[p];
    return res;
}

int main(){
    read(n);
    for(rint i=1;i<=n;++i) read(a[i]);
    read(m);
    for(rint i=1;i<=m;++i){
        read(q[i].l); read(q[i].r); q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);

    int pow=1;
    for(rint i=1;i<=m;++i){
        for(rint j=pow;j<=q[i].r;++j){
            if(vis[a[j]]) modify(vis[a[j]],-1);
            modify(j,1);
            vis[a[j]]=j;
        }
        pow=q[i].r+1;
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }

    for(rint i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

小结

好想好写跑得快（注意常数），是树状数组的巨大优势，认清了需要维护的操作之后树状数组一般是个不错的选择。本题的标准做法应该就是树状数组，因为无论哪方面都跟树状数组的核心思想和可支持的操作契合度很高，并且码量短、空间小、耗时少。尽管这样还是想种一棵线段树，于是才有了以下的内容。

线段树解法

思路

线段树是支持区间修改区间查询的东西……用来做单点修改有点大炮轰蚊子，还慢。不过谁让我闲呢，好在不会T掉，只是比树状数组要慢的太多了，所以不推荐使用。看了一些题解的评论区发现有许多想用线段树做的同学，但是没找到相应的题解，就让这篇解题报告来补上这个空吧。

其实线段树的思路跟树状数组的思路几乎完全一样，只是对于不同的操作有不同的写法而已。比如对于询问区间排序、维护最右端的贝壳位置、忽略无用位置、求前缀和……完全是一样的。所以这部分的思路讲解会偏少，主要会着眼于线段树本身的操作和细微的调整。如果线段树的基础很好，也可以只大致过一遍。

因为线段树占的空间比较大，所以我们所有的数组都开了四倍大小，不这样做会RE或者WA掉。

线段树的话目前我是没看到有其他人跟我写成一个鬼样子，大概就是上来三行宏，后面就开始疯狂输出（?

#define root 1,n,1 // 树根的左端点右端点以及节点编号
#define lson l,mid,rt<<1 // 节点rt的左儿子，各参数意义同上
#define rson mid+1,r,rt<<1|1 // 结点rt的右儿子，各参数意义同上

这种写法我个人看来比较标准化和格式化，用在函数的参数里也可以减小一点思维难度。只是这样就限制了变量的命名必须是mid和rt，需要注意。并且每个函数都有了三个固定的参数l，r，rt用于格式化操作。

总之下面就是差别并不太大的几个板子函数，因为作了一些微调所以我们每个都捞出来讲讲：

重点来了！接下来要讲的就是一个vector数组：vis[]。这也是线段树做法唯一区别于树状数组的地方，这个vis[]数组应该是整个代码最难理解的部分。这里先放两段vis[]数组的使用代码：

sort(q+1,q+m+1,cmp);
for(rint i=1;i<=m;++i) vis[q[i].r].push_back(i); // 确定每一个问题的访问顺序 

for(rint i=1;i<=n;++i)
    // ...codes...
    for(rint j=0;j<vis[i].size();++j){
        int tmp=vis[i][j];
        ans[q[tmp].id]=query(root,q[tmp].l,q[tmp].r); // 按问题的原序(id)存好ans
    }

两段代码并不能说明什么问题，所以这里列一张样表，来解释这个数组的工作原理：

这张表的第一行，加粗部分是每个vector数组的编号。每一列除了第一行下面挂着的数字，就代表着每一个询问的访问顺序。这张表是由第一段代码生成的，按照排序后的区间右端点作为第一关键字，让以点q[i].r为右端点的询问区间挂在以该点为编号的vector里，便于第二段代码调用。此时这个vis[]数组的第一维其实就是点的编号，每个点下面挂的数字就是每个询问的访问顺序。第二段代码中的...codes...部分进行的是线段树操作，在每个点操作完毕时遍历该点下挂的询问访问顺序，按照其保存的原序存储ans数组。

这确实有些难理解，而且讲起来也很拗口，概念也容易混淆。但是如果理解了会非常有意思，实在不行可以手动模拟一下，便于弄清每一步操作的含义。

接下来有个lst[]数组，其意义参考上文树状数组思路中的vis[]数组。

然后没什么好说的，用线段树的函数对每个点进行一些操作，我们就可以快乐输出然后return 0了。

一个意外

Upd on Nov.3

一觉醒来发现rqy评论了我，拿过来看看，说是线段树做法既然开了vis数组就没必要再对于询问区间排序了。突然发现这一行排序其实是复制树状数组代码时候无意间忘了删除的，因为vis数组实际上实现了跟排序一样的作用，再排一遍其实没必要。但是很奇妙的事情出现了，当我删除了这行sort后，交上去T了两个点……（不吸氧）

“没道理啊，应该更快才对啊，这可少了一个sort啊。”

以下是与rqy的记录：

rqy 可能是

rqy cache相关？

Maplef 噫（

rqy 就是你原本那样会连续插入到同一个vector里

Maplef 嗯对

rqy 理论上来说是更快的

Maplef 哦意思就是说

Maplef 每次插入到不同的vector里耗时会多……？

Maplef 不对啊……

Maplef 这跟耗时多少有很大关系吗qaq

rqy 是说

rqy 就是

rqy 你操作一段内存的时候就会把它加载到缓存里

rqy 所以反复跳来跳去是比连续访问慢不少的

rqy 但我没想到这个时间差超过一个sort

Maplef wua……

Maplef 居然这样

Maplef 对啊

rqy 嘛

Maplef 我也觉得它不该比sort慢

Maplef qwq

Maplef 怎么这样

这个问题现在自己也搞不明白，只能说误打误撞多写了个sort免于超时，所以把它归在“一个意外”里。没想到跳跃访问不同的vector耗时比一个sort还要多，这也许可以成为写程序的一个注意点：在频繁访问不同段内存的时候，不妨可以考虑将访问顺序重新排序，以避免更多的耗时。

总代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define rint register int
#define maxn 1000010

#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;

int n,m;
int a[maxn<<2],lst[maxn<<2];
int tree[maxn<<2],ans[maxn<<2];
vector<int> vis[maxn<<2];

struct QUE{
    int l;
    int r;
    int id;
}q[maxn<<3];

inline void read(int &x){
    char ch=getchar();int f=1;x=0;
    while(!isdigit(ch) && ch^'-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}

inline bool cmp(const QUE &a,const QUE &b){
    return a.r<b.r;
}

void update(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void build(int l,int r,int rt,int tar){
    if(l==r && l==tar){
        tree[rt]=1; return;
    }
    int mid=(l+r)>>1;
    if(tar<=mid) build(lson,tar);
    else build(rson,tar);
    update(rt);
}

void modify(int l,int r,int rt,int tar){
    if(l==r && l==tar){
        tree[rt]=0; return;
    }
    int mid=(l+r)>>1;
    if(tar<=mid) modify(l,mid,rt<<1,tar);
    else modify(mid+1,r,rt<<1|1,tar);
    update(rt);
}

int query(int l,int r,int rt,int nowl,int nowr){
    if(l==nowl&&r==nowr) return tree[rt];
    int mid=(l+r)>>1;
    if(nowr<=mid) return query(lson,nowl,nowr);
    else if(mid<nowl) return query(rson,nowl,nowr);
    else return query(lson,nowl,mid)+query(rson,mid+1,nowr);
}

int main(){
    read(n);
    for(rint i=1;i<=n;++i) read(a[i]);
    read(m);
    for(rint i=1;i<=m;++i){
        read(q[i].l); read(q[i].r);
        q[i].id=i;
    }

    sort(q+1,q+m+1,cmp);
    for(rint i=1;i<=m;++i) vis[q[i].r].push_back(i);

    for(rint i=1;i<=n;++i){
        if(!lst[a[i]]){
            lst[a[i]]=i;
            build(root,i);
        }
        else{
            modify(root,lst[a[i]]);
            lst[a[i]]=i;
            build(root,i);
        }

        for(rint j=0;j<vis[i].size();++j){
            int tmp=vis[i][j];
            ans[q[tmp].id]=query(root,q[tmp].l,q[tmp].r);
        }
    }

    for(rint i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

小结

线段树码量是大了点，但是支持更多的操作（也更慢），拿来练练树状数组的题目倒也未尝不可。只是要注意区别和理解两种方法里不同的操作：一个用pow来指向位置，一个用vis[]数组事先存好访问顺序。两种做法因个人喜好而定，写出不同的操作一来是为了避免重复之嫌，二来也希望可以给各位带来更广阔的思考空间。

鸣谢

_rqy提供的新思路以及引出的新问题。

写在后面

本文在深夜写就，时间有些仓促，讲解的内容也或许蜻蜓点水。如有讲的不明白或者错误（错字）的地方恳请私信我或评论指出。

放一篇以前的解题报告：时间复杂度 解题报告。

最后感谢你能够看到这里，我们一起，为了未来的所有。