题意

• 对于一个序列，如果某个数字出现两次及以上就可以全部拿取
• 否则就不能拿取，给出长为n的序列，有m次查询
• 每次查询会给出一个区间，回答最多拿取多少种数字

思路

• 附一个别的大佬的blog，推导很详细
• 对于一个数字，可不可以拿取，取决于到当前位置该数字有没有出现超过两次，也就是一个数出现意味着左端点落在上一次和上上次之间可得的数量增加1
• 离线查询，按照查询右端点排序
• 维护一个树，记录处理到当前位置，每个点可得的最大值
• 这个树设计两个操作，对于某个点值的查询，对于某个区间的整体加一
• 可以维护这个树的差分数组，单点的查询变为前缀和，区间的增加变为两个单点的修改，这样就不用开线段树可以用树状数组

代码

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

struct Q{
    int l,r,id,ans;
}q[2020202];
int a[2020202],tree[2020202];
int last1[2020202],last2[2020202];
int n,c,m;

int lowbit(int x){ return x&(-x); }
void add(int x,int val){
    while(x<=n){
        tree[x]+=val;
        x+=lowbit(x);
    }
}
int sum(int x){
    int s=0;
    while(x>0){
        s+=tree[x];
        x-=lowbit(x);
    }
    return s;
}


bool cmp1(Q x,Q y){
    return x.r<y.r;
}

bool cmp2(Q x,Q y){
    return x.id<y.id;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> c >> 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+1+m,cmp1);
    vector<int>mp(c+10);
    int pos=1;
    for(int i=1;i<=n;i++){
        mp[a[i]]++;
        if(mp[a[i]]>=2){
            add(last2[a[i]]+1,1);
            add(last1[a[i]]+1,-1);            
        }
        last2[a[i]]=last1[a[i]];
        last1[a[i]]=i;
        while(pos<=m&&q[pos].r==i){
            q[pos].ans=sum(q[pos].l);
            pos++;
        }
    }
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;i++){
        cout << q[i].ans <<endl;
    }
    return 0;
}