HH的项链
看到这题，我首先想到了用flag[]数组标记，很明显这是必需的。
但随着代码进行，又会遇到一个问题：如1 2 1 2，如果按照正常标记后面两个就不会被标记，那遍历3到4时，结果为0。
顺着思路想，如果我们在用完一次后把它丢掉，重新遍历，这也就导致我们必须要采用一种有序遍历，从而让后面的更新不会影响前面的结果，同时，我们也要每次更新完数据，自动计算结果并保存，后面更新就不再计算（离线）。到这，这道题的大体思路明了。
这里了解到几个新东西。
离线
在第一次更新到这个状态时，计算结果，即使后面再更新数据，也不再改变结果。
在线
每次数据更新，重新计算结果。
接下来就是代码了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
struct lmy//多个变量排序时可控
{
int l,r;
int id;
bool operator <(const lmy a)
{
return r<a.r;//以右边界大小排序
//遍历完后处理的数据不受影响
}
}q[N];
int a[N];
int mark[N];//mark[i]表示i上一次出现的位置
int c[N];
int ans[N];//保存结果
int n,m;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int t)
{
while(x<=n)
{
c[x]+=t;
x+=lowbit(x);
}
}
int getsum(int x)
{
int ans=0;
while(x)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+1+m);
int last=1;//上次查询的结尾+1
for(int i=1;i<=m;i++)
{
for(int j=last;j<=q[i].r;j++)
{
if(mark[a[j]])
//如果为0，它为第一个数
//不为0，则有上一个数
{
add(mark[a[j]],-1);//上一个数置0
}
add(j,1);
mark[a[j]]=j;//标记为上一个数
}
last=q[i].r+1;
ans[q[i].id]=getsum(q[i].r)-getsum(q[i].l-1);
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}