SDOI2009 HH的项链

暴力莫队树状数组

本蒟蒻的第一篇博客对博客的格式还不是很熟悉…
我们回到正题，现在先来看一下题面

题目描述

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

输入输出格式

输入格式：

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

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

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

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

输出格式：

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

解题分析

暴力

初看题目，打暴力肯定是会T的（废话），初步估计40分…
暴力枚举询问的空间，每次清空用于记忆的数组…

莫队 80分

看到这道题其实很容易想到是莫队的…
莫队是基于分块思想的一种算法，很好理解…
我们先把询问离线，之后再排个序…
对于区间 l ~ r ,如果我们已知在这个区间里不同的贝壳种类有sum个，那么对于区间 l ~ r+1,或者区间 l-1 ~ r 就可以在O（1）的时间复杂度下得出对于 l-1 ~ r 的sum的值
所以我们把询问的区间排个序，使 l 和 r 尽可能少的移动，就可以比暴力少算很多次，这一段很好理解吧
但是考虑最不优的询问，如果询问的区间一个在数列的最左边，一个最右边，这样进行 l 和 r 的转移，时间复杂度就是要O（n)，还不如写暴力
因此我们用上分块的思想，把这一串数列分成 sqrt( n ) 块，这样时间复杂度就会降低很多。（分块不懂？！那你还学莫队！！）
实际上莫队是一种近似暴力的方法，时间复杂度比暴力客观得多，但是很不巧这道题的数据很强莫队卡不过去只有80分…
贴出莫队代码氧气优化80分

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=500010;
int n,m,le=1,ri=1;
int a[N],clo[2*N],sum=1,size,ans[N],belong[N];
struct que{
    int l,r,id;
    inline bool operator <(const que &rhy) const{return belong[l]==belong[rhy.l]?r<rhy.r:belong[l]<belong[rhy.l];}
}q[N];
	
inline void move(int x,int opt){
    clo[a[x]]+=opt;
    if(clo[a[x]]==0&&opt==-1) sum--;
    if(clo[a[x]]==1&&opt==1) sum++;
}

int main(){
    scanf("%d",&n);size=sqrt(n);
    rep(i,1,n) scanf("%d",&a[i]);rep(i,1,n) belong[i]=(i-1)/size+1;
    scanf("%d",&m);
    rep(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+1+m);clo[a[1]]++;
    rep(i,1,m){
        while(le<q[i].l){move(le,-1);le++;}
        while(le>q[i].l){le--;move(le,1);}
        while(ri>q[i].r){move(ri,-1);ri--;}
        while(ri<q[i].r){ri++;move(ri,1);}
        ans[q[i].id]=sum;
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

-不熟悉Makedown的我觉得这样应该勉强能看排版丑勿介

正解树状数组 100分

我觉得其实很容易就会想到用树状数组或者线段树，但是我好像并不会维护所以才去打的莫队…莫队加了优化也是可以过的可是我不会（逃
如果知道怎么去维护树状数组其实题目就已经完成了（废话）
我们来看一组数列 1 3 4 2 1 ，我们可以发现，对于询问区间 r = 5 的所有询问中（ l <= r ), 因为这个数列的第五个为 1 ，而第一个也是 1 ，所以对于 r = 5 而言，第一个数是没有多大意义的…
我觉得很好理解…所以我们可以对所有询问离线，再对 r 进行排序，用树状数组维护（好像也不需要维护），只需要对于每次询问求前缀和即可
单点增加与查找的函数都是模板没有什么变化，我们只需要想到如何用树状数组表示出前 i 个贝壳颜色的种类
我们用 last 数组表示出该颜色在此之前第一次出现的位置， vis 数组用于表示 i 颜色是否出现过
很容易得出 query（r)-query(l-1)即为答案但是如何不出错呢，我们要这样动态更新呢
只要在左端点之前出现过，就加上，想通这一点，只需要最基础的树状数组就行了
洛谷吸氧 424 ms AC100分

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=1000010;
int n,m;
int v[N],tree[N],ans[N],vis[N],last[N];
struct question{
    int l,r,id;
    inline bool operator < (const question &rhy)const {return r!=rhy.r?r<rhy.r:l<rhy.l;}
}q[500010];

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

inline void add(int x,int k){while(x<=n) tree[x]+=k,x+=lowbit(x);}

inline int query(int x){int ans=0;while(x>0){ans+=tree[x];x-=lowbit(x);}return ans;}

int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&v[i]);scanf("%d",&m);
    rep(i,1,m) {scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}
    sort(q+1,q+1+m);
    int now=0;
    rep(i,1,m){
        while(now<q[i].r) {
            now++;
            if(!vis[v[now]]) vis[v[now]]=1,last[v[now]]=now,add(now,1);
            else add(last[v[now]],-1),add(now,1),last[v[now]]=now;
        }
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

感谢资瓷欢迎围观指正

联系qq： 953559040

微博： IncinblePan

洛谷： SherlockPan

暴力 莫队 树状数组