区间不同元素个数
可以用莫队，主席树，树状数组解决
SPOJ DQUERY - D-query(树状数组，离线查询,区间不同元素个数)
题意是给你n个数，再给你m个查询，每次查询一个[l,r],求询问的区间内有多少种不同的数字。
这个题可以使用离线处理+树状数组的方式来处理。
首先记录一下每一个查询，然后按照查询的右端点从小到大排序，然后然后依次处理每个区间 树状数组维护以r为结尾的区间元素种类数，从下标1开始扫描，扫描到排序后的第一个区间的右端点，如果当前数字出现过，就在树状数组原先对应位置-1,然后在新的对应位置+1，然后更新当前元素出现的位置。然后每一个区间的结果就是新的sum[r]-sum[l-1],离线保存起来.
代码(树状数组)
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 3e5 + 10;
const int inf = 0x3f3f3f3f;
int a[N], n, m, ans[N], c[N];
map<int, int> mp;
int lowbit(int x)
{
return x & -x;
}
void add(int i, int k)
{
while (i <= n)
{
c[i] += k;
i += lowbit(i);
}
}
int sum(int i)
{
int res = 0;
while (i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
struct node
{
int l, r, id;
} query[N];
bool cmp(node x, node y)
{
return x.r < y.r;
}
int main()
{
// freopen("in.txt", "r", stdin);
while (~scanf("%d", &n))
{
mem(c, 0);
mp.clear();
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%d%d", &query[i].l, &query[i].r);
query[i].id = i;
}
sort(query, query + m, cmp);
int cur = 1; //从下标为1的位置开始扫描
for (int i = 0; i < m; i++)
{
for (int j = cur; j <= query[i].r; j++)
{
if (mp.find(a[j]) != mp.end())
{
add(mp[a[j]], -1);
}
add(j, 1);
mp[a[j]] = j;
}
cur = query[i].r + 1;
ans[query[i].id] = sum(query[i].r) - sum(query[i].l - 1);
}
for (int i = 0; i < m; i++)
printf("%d\n", ans[i]);
}
return 0;
}
给出一个有n个数的序列，然后给出m组询问，每组询问一个区间$[l,r]$,求这个区间内包含多少种不同的数。
主席树可以离线处理，在线查询，就是不需要把询问都读进来，而是可以及时回答每一个询问。当输入数据被根据上一次查询的答案加密过后，莫队和离线操作就无用武之地了。这时候我们可以考虑转化问题。
对于每一个点，都制作一个next[i]表示在这个点之后最近的颜色相同的点，如果没有就设为n+1，记一下队头$O(N)$扫一遍就好了
考虑区间查询l~r之间的颜色种数，其实就是求所有满足(l<=i<=r,next[i]>r)的个数，因为如果某个点的next已近超出了这个区间的范围，就说明这个点对答案产生贡献了。
这个时候问题就已近被转化为给定一个序列，求区间l~r之间权值大于r的个数。
那么我们对于每个点都在可持久化的权值线段树中构造一条新的线段树链就好了，查询就是常规的权值线段树的查询。
对于每个点都要新建一条最多$log_2N$个点的链，空间复杂度$nlog_2n$；对于每次询问最多递归深度为$log_2n$层，时间复杂度$mlog_2n$。
代码(主席树)
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int N=1e6+10;
int n,m,p,node_cnt;
int head[N],nex[N],a[N];
int rt[N],lc[N<<5],rc[N<<5],sum[N<<5];
void build(int &t,int l,int r)
{
t=++node_cnt;
if(l==r) return;
int mid=(l+r)>>1;
build(lc[t],l,mid);
build(rc[t],mid+1,r);
}
int modify(int o,int l,int r)
{
int oo=++node_cnt;
lc[oo]=lc[o];
rc[oo]=rc[o];
sum[oo]=sum[o]+1;
if(l==r) return oo;
int mid=(l+r)>>1;
if(p<=mid)
lc[oo]=modify(lc[oo],l,mid);
else
rc[oo]=modify(rc[oo],mid+1,r);
// sum[oo] = sum[lc[oo]] + sum[rc[oo]];
return oo;
}
//u,v代表当前节点的rt
int query(int u,int v,int l,int r,int k)//返回区间u到v,>=k的个数
{
int mid=(l+r)>>1,ans=0;
if(l==r) return sum[v]-sum[u];
if(k<=mid)
{
int x=sum[rc[v]]-sum[rc[u]];
ans+=query(lc[u],lc[v],l,mid,k)+x;
}
else
ans+=query(rc[u],rc[v],mid+1,r,k);
return ans;
}
void init()
{
mem(head,0);
mem(nex,0);
node_cnt=0;
}
int main()
{
scanf("%d",&n);
init();
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(head[a[i]])
nex[head[a[i]]]=i;
head[a[i]]=i;
}
for(int i=1; i<=n; i++)
if(!nex[i])
nex[i]=n+1;
build(rt[0],1,n+1);
for(int i=1; i<=n; i++)
{
p=nex[i];
rt[i]=modify(rt[i-1],1,n+1);
}
int l,r;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(rt[l-1],rt[r],1,n+1,r+1));
}
return 0;
}
/*
6
1 2 3 4 3 5
3
2 6
*/
莫队算法解决见莫队算法章节