疯狂的颜色序列

一句话题意：强制在线版 HH 的项链。

前置-主席树

本质就是动态开点的线段树，支持可持久化。

在有修改的题目中，通常是先建一棵普通线段树，修改操作变为每次新建一个将更改的节点，每次新增一条链，在它上面操作，记录根节点为时间戳，需要在哪个版本操作就动以其时间戳为根的哪棵树。

当然静态问题也可以用主席树解决，如区间第 \(k\) 小，以及这道区间数颜色等，做法就变为了以序列里的每个元素为根分别新建节点，此时我们若求 \(\left[l,r\right]\) 内的信息只需用 \(r\) 这棵树上的信息减去 \(l-1\) 这棵树上的信息即可。

图画起来不难，手模一下加速理解。

思路

如果不强制在线的话，这道题方法还是蛮多的，最简单且好理解的就是莫队做法。

考虑在这道题上使用主席树（虽然但是如果没有签我也想不到）。首要问题是，每个节点权值存什么，怎么维护。

我们考虑，一个点有贡献当且仅当其颜色在这段区间内首次出现。有了这个结论，我们可以在输入时就记录每个点的颜色上次出现的位置。这样一来，得出答案就可以通过判断该区间内每个点的颜色上次出现的位置是否在此区间，即若上次出现的位置在 \(\left[0,l-1\right]\) 内，该点是有贡献的。那么方法就出来了，我们记录每个点成为“上个相同颜色的点”的次数，只需要统计第 \(r\) 棵树与第 \(l-1\) 棵树在 \(\left[0,l-1\right]\) 范围内权值的差即可得出答案。

细节

所有在整个序列中首次出现的颜色上次出现位置都是 0，因此线段树维护范围是 \(\left[0,n\right]\)。

整体上看，属于加了主席树细节操作的支持单点修改区间查询的线段树，还是很好实现的。

关于数组大小，只要不是区间修改标记永久化的主席树，开 20 倍空间差不多就够了，不过这类题空间一般给的很宽松，个人习惯开 32 倍，即右移 5 位。

实现

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
using namespace std;
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define qr qr()
const int Ratio=0;
const int N=5e5+5;
int n,m,ans;
int las[N],rot[N],cnt;
int son[N<<5][2],va[N<<5];
namespace Wisadel
{
    #define ls (son[rt][0])
    #define rs (son[rt][1])
    #define mid ((l+r)>>1)
    int Wclone(int rt)
    {
        son[++cnt][0]=ls,son[cnt][1]=rs;
        va[cnt]=va[rt]+1;
        return cnt;
    }
    int Wupd(int rt,int l,int r,int x)
    {
        rt=Wclone(rt);
        if(l==r) return rt;
        if(x<=mid) ls=Wupd(ls,l,mid,x);
        else rs=Wupd(rs,mid+1,r,x);
        return rt;
    }
    int Wq(int u,int v,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y) return va[v]-va[u];
        int res=0;
        if(x<=mid) res+=Wq(son[u][0],son[v][0],l,mid,x,y);
        if(y>mid) res+=Wq(son[u][1],son[v][1],mid+1,r,x,y);
        return res;
    }
    short main()
    {
        n=qr,m=qr;
        fo(i,1,n)
        {
            int x=qr;
            rot[i]=Wupd(rot[i-1],0,n,las[x]);
            las[x]=i;
        }
        fo(i,1,m)
        {
            int l=qr,r=qr;
            l=(l+ans)%n+1,r=(r+ans)%n+1;
            if(l>r) swap(l,r);
            printf("%d\n",ans=Wq(rot[l-1],rot[r],0,n,0,l-1));
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~