题解：P7764 [COCI 2016/2017 #5] Poklon

· · 题解

思路

这题看题面非常莫队（多写一点莫队就知道了），数据也不大，莫队能过，所以写正常莫队就行了。注意奇偶块优化别写错了。还有一点，这题数组中元素小于 10^9 不能直接用数组存每个数的出现次数，要离散化，如果不会可以看我的代码，但是 map 常数有点大，如果数据大建议换一种方式离散化。其他细节可以看代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct A{
    int l,r,k,id;
}q[500005];
bool cmp(A x,A y){//奇偶块优化 
    if(x.k!=y.k) return x.l<y.l;
    if(x.k%2==1) return x.r<y.r;
    return x.r>y.r;
}
int n,Q,a[500005],b[500005],l=1,r,cnt,ans[500005],v[500005],kuai,ll,rr;
map<int,int> mp;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>Q;
    kuai=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    for(int i=1;i<=Q;i++){
        cin>>q[i].l>>q[i].r;
        q[i].k=(q[i].l-1)/kuai+1;//记哪一个块，用来奇偶块优化 
        q[i].id=i;//优化后问题顺序会变，所以要记提问的原位置 
    }
    sort(q+1,q+1+Q,cmp);//奇偶排序 
    sort(b+1,b+1+n);//排序离散化 
    for(int i=1,j=1;i<=n;i++){
        if(b[i]!=b[i-1]){
            mp[b[i]]=j;//记录离散化结果 
            j++;
        }
    }
    for(int i=1;i<=n;i++) a[i]=mp[a[i]];//该原数组为离散化后的 
    for(int i=1;i<=Q;i++){
        ll=q[i].l,rr=q[i].r;
        while(r<rr){//顺序很重要，可以记一下 
            r++;
            if(v[a[r]]==2) cnt--;
            v[a[r]]++;
            if(v[a[r]]==2) cnt++;
        }
        while(l>ll){
            l--;
            if(v[a[l]]==2) cnt--;
            v[a[l]]++;
            if(v[a[l]]==2) cnt++;
        }
        while(l<ll){
            if(v[a[l]]==2) cnt--;
            v[a[l]]--;
            if(v[a[l]]==2) cnt++;
            l++;
        }
        while(r>rr){
            if(v[a[r]]==2) cnt--;
            v[a[r]]--;
            if(v[a[r]]==2) cnt++;
            r--;
        }
        ans[q[i].id]=cnt;//注意记在原位置上而不是现在的位置i (我因为这个考试挂了 
    }
    for(int i=1;i<=Q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}