[SDOI2009] HH的项链 | 莫队模板

题目链接：戳我

题意：求区间中不同颜色的种类数

因为是要过知识点，所以又把这题拿出来做了一遍。。。。。。这里就写两种方法吧

主席树做法

设pre[i]为第i个点上的颜色在前面序列中出现的最晚的一次的位置+1，那么就可以将问一个区间内有多少种颜色转化为——问一个区间内上有多少个点的pre在当前区间左端点之前。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 50010

using namespace std;

int n,m,cnt;

int a[MAXN<<5],pre[MAXN<<5],last[MAXN<<5],rt[MAXN<<5];

struct Node{int ls,rs,v;}t[MAXN<<5];

inline void modify(int &x,int f,int l,int r,int pos,int k)

{

    x=++cnt;

    t[x]=t[f];t[x].v+=k;

    if(l==r) return;

    int mid=(l+r)>>1;

    if(pos<=mid) modify(t[x].ls,t[f].ls,l,mid,pos,k);

    else modify(t[x].rs,t[f].rs,mid+1,r,pos,k);

}

inline int query(int x,int f,int l,int r,int ll,int rr)

{

    if(ll<=l&&r<=rr) return t[x].v-t[f].v;

    int mid=(l+r)>>1;

    int cur_ans=0;

    if(ll<=mid) cur_ans+=query(t[x].ls,t[f].ls,l,mid,ll,rr);

    if(mid<rr) cur_ans+=query(t[x].rs,t[f].rs,mid+1,r,ll,rr);

    return cur_ans;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    freopen("ce.out","w",stdout);

    #endif

    scanf("%d",&n);

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

    {

        scanf("%d",&a[i]);

        pre[i]=last[a[i]]+1;

        last[a[i]]=i;

        modify(rt[i],rt[i-1],1,n,pre[i],1);

    }

    scanf("%d",&m);

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

    {

        int u,v;

        scanf("%d%d",&u,&v);

        printf("%d\n",query(rt[v],rt[u-1],1,n,1,u));

    }

}

莫队做法

莫队有些奇奇怪怪的块的大小，但是我不是特别会，所以就记成一般的根号的大小吧。

然后排序的时候以所在块的编号为第一关键字，右端点为第二关键字。

写的时候注意一下i++和++i的区别就可以了qwq