提出 #29891372

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

const int B=316;
int n,q,a[100005],c[100005],res,ans[1000005];
pair<pair<int,int>,int> qs[1000005];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>qs[i].first.first>>qs[i].first.second;
        qs[i].second=i;
    }
    sort(qs+1,qs+1+q,[&](const pair<pair<int,int>,int>& a,const pair<pair<int,int>,int>& b){
        if(a.first.first/B!=b.first.first/B)return a.first.first/B<b.first.first/B;
        if(a.first.second!=b.first.second)return a.first.second<b.first.second;
        return a.second<b.second;
    });
    int l=1,r=0;
    for(int i=1;i<=q;i++){
        int ql,qr;
        tie(ql,qr)=qs[i].first;
        while(r<qr){
            ++r;
            res+=c[a[r]]&1;
            ++c[a[r]];
        }
        while(l>ql){
            --l;
            res+=c[a[l]]&1;
            ++c[a[l]];
        }
        while(r>qr){
            --c[a[r]];
            res-=c[a[r]]&1;
            --r;
        }
        while(l<ql){
            --c[a[l]];
            res-=c[a[l]]&1;
            ++l;
        }
        ans[qs[i].second]=res;
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';

    return 0;
}

提出情報

ジャッジ結果