P7764题解
题目
这道题可以用离线树状数组来做，我们先将每个询问存下来，排序后对其进行修改与求和。
对于修改时遇到的一个数，有 4 种情况。
-
当这个数第一次出现。这时它还不能做出贡献，只需标记一下它出现过一次就行了。
-
当这个数第二次出现。这时我们如果给这一位的贡献加 1，那就会多算一些，我们只能给它前一次出现的位置加 1，同时标记它出现了 2 次。
-
当这个数第三次出现。同理，给上一次出现的位置的贡献加 1。但是，这样的话往前 2 位以前就会多出 1，这样，我们就需要将上上次出现的位置的贡献减掉 2。还有要记得标记它出现 3 次了。
-
当这个数出现了 4 次级以上时。对于前两次出现的位置的处理同上，但是如果只这样也不行，还需将上上上次出现的位置的贡献归零，即加 1。
还有的一些细节在代码中讲解。
代码
#include<bits/stdc++.h>
using namespace std;
int n,q,b[500005];
struct Node{
int a,b,c,x;//a表示上次出现的位置，b表示上上次出现的位置，c表示上上上次出现的位置，x表示出现了几次
};
map<int,Node>m;//Node结构体用来存储每一个值的出现次数及前几次出现的位置
int lowbit(int x){return x&-x;}//lowbit函数，求正整数的二进制状态下的最低位的1的权值
struct node{
int l,r,id,ans;
bool operator<(const node &t)const{//重载node结构体的“<”运算符
return id<t.id;
}
}a[500005];//存储询问
struct BIT{//树状数组
int c[500005];//c是树状数组的节点
void Add(int x,int y){//将x这个位置的贡献加y
while(x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
int Getsum(int x){//求x以前的前缀和
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int Getsum(int l,int r){//区间查询
return Getsum(r)-Getsum(l-1);
}
}T;
bool cmp(const node a,const node b){
return a.r<b.r;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);//读入数据
for(int i=1;i<=q;i++){
scanf("%d%d",&a[i].l,&a[i].r);//读入询问
a[i].id=i;
}
sort(a+1,a+q+1,cmp);//将询问排序
int cnt=1;
for(int i=1;i<=q;i++){
for(;cnt<=a[i].r;cnt++){//对每个询问的右端点以前的未处理的所有元素进行处理操作
if(m.count(b[cnt])==1){
if(m[b[cnt]].x==1){//已有1次出现，即这是第2次出现
T.Add(m[b[cnt]].a,1);
m[b[cnt]].x++;//标记次数
m[b[cnt]].b=m[b[cnt]].a;
m[b[cnt]].a=cnt;
}
else if(m[b[cnt]].x==2){//已有2次出现，即这是第3次出现
T.Add(m[b[cnt]].a,1);
T.Add(m[b[cnt]].b,-2);
m[b[cnt]].x++;//标记次数
m[b[cnt]].c=m[b[cnt]].b;
m[b[cnt]].b=m[b[cnt]].a;
m[b[cnt]].a=cnt;
}
else{//出现次数大于等于4
T.Add(m[b[cnt]].a,1);
T.Add(m[b[cnt]].b,-2);
T.Add(m[b[cnt]].c,1);
m[b[cnt]].c=m[b[cnt]].b;
m[b[cnt]].b=m[b[cnt]].a;
m[b[cnt]].a=cnt;
//因为出现的次数大于等于4了，所以不需要标记了。
}
}
else{//以前还没出现过，即这是第1次出现
m[b[cnt]].x++;//标记次数
m[b[cnt]].a=cnt;
}
}
a[i].ans=T.Getsum(a[i].l,a[i].r);
}
sort(a+1,a+q+1);
for(int i=1;i<=q;i++){
printf("%d\n",a[i].ans);
}
return 0;
}