题解：洛谷 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;
}