P1972 [SDOI2009] HH的项链
https://www.luogu.com.cn/problem/P1972?
本博客将以该题目为例进行介绍
方法1：树状数组
树状数组需要结合离散化处理，我们观察到一个性质，随着右端点的右移，每一种元素的贡献位置（这里指存在贡献的位置，如：1 2 3 1 这组数据，内1元素的贡献可以用4位置提供1次贡献，而1位置的元素贡献为0），因为右端点不断右移，所以不需要考虑查询区间存在如下情况：
?在上图中，假设7位置的1提供了贡献，此时肯定右端点位置，故上图区间
的答案会在右端点在6时候得到
这样处理完后，就可以n^2logn时间预处理出n长度的序列每个区间的答案了
for(int j=1;j<=n;j++)
{
if(pre[a[j]]) add(pre[a[j]],-1);
add(j,1); pre[a[j]]=j;
for(int i=1;i<=n;i++)
sum[i][j]=query(j)-query(i-1);
}粘一个别人的题解：
?方法2：莫队
莫队基操了吧，过
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1000005;
const int maxm=1000005;
inline int read()
{
int x=0,y=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
struct quer
{
int l,r;
int pos;
}ask[maxm];
int m,n,a[maxn],c[maxn];
int pre[maxn];
int ans[maxn];
bool cmp(quer aa,quer bb)
{return aa.r<bb.r;}
int lowbit(int x) {return x&(-x);}
void add(int now,int x)
{
for(;now<=n;now+=lowbit(now)) c[now]+=x;
return ;
}
int query(int now)
{
int sum=0;
for(;now;now-=lowbit(now)) sum+=c[now];
return sum;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
m=read();
memset(pre,0,sizeof(pre));
for(int i=1;i<=m;i++)
{
ask[i].l=read();
ask[i].r=read();
ask[i].pos=i;
}
sort(ask+1,ask+1+m,cmp);
int now=1;
for(int i=1;i<=m;i++)
{
for(int j=now;j<=ask[i].r;j++)
{
if(pre[a[j]]) add(pre[a[j]],-1);
add(j,1);
pre[a[j]]=j;
}
now=ask[i].r+1;
ans[ask[i].pos]=query(ask[i].r)-query(ask[i].l-1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}?方法3：主席树
对于每一个位置的元素，记录一下它这种元素后面第一次出现的位置，记为nxt[i]
那么对于一个询问[l,r]，我们就是求，nxt[i]>r 的位置i的个数
那就以i位置权值为nxt[i]建一颗权值主席树，查询时候，
?按照上面查询即可（其实就是统计区间内权值小于k的数的个数
?
