题解：洛谷 P4113 [HEOI2012] 采花

题目https://www.luogu.com.cn/problem/P4113

运用类似于P1972 [SDOI2009] HH的项链的操作，将数据离线下来处理。

按照区间右端点从小到大排序。

问题是数量大于等于 的时候才能算进去。

于是乎我们用两个数组维护倒数第二次出现和最后一次出现的地方。

每次在树状数组中仅保留倒数第二次出现的贡献。

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,color,m,a[2000005],ans[2000005],c[2000005],l[2000005],r[2000005];
bool vis[2000005];
struct node{int l,r,id;bool operator<(const node &T)const{return r<T.r;}
}q[2000005];
int lowbit(int x){return x&(-x);
}
int query(int x){int sum=0;while(x){sum+=c[x];x-=lowbit(x);}return sum;
}
void modify(int x,int val){while(x<=n){c[x]+=val;x+=lowbit(x);}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>color>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;}sort(q+1,q+m+1);for(int i=1,j=1;i<=m;i++){for(;j<=q[i].r;j++){if(!vis[a[j]]){ // 如果当前颜色是第一次出现vis[a[j]]=true;l[a[j]]=j; // 仅标记不做操作}else if(!r[a[j]]){ // 第二次出现r[a[j]]=j;modify(l[a[j]],1); // 加上贡献}else{ // 重复出现modify(l[a[j]],-1);modify(r[a[j]],1);l[a[j]]=r[a[j]]; // 替换r[a[j]]=j;}}ans[q[i].id]=query(q[i].r)-query(q[i].l-1);}for(int i=1;i<=m;i++){cout<<ans[i]<<'\n';}return 0;
}