SP23776

Eltaos_xingyu · 2024-01-17 16:14:13 · 题解

不会主席树。

离线版本可以莫队 + 值域分块。

在线的话，这里提供两种分块方法。

O(m\sqrt{n\log n})

整块二分查找，散块暴力查询，取块长 B=\sqrt {n\log n}，得到复杂度 O(m\sqrt{n\log n})，若取块长 B=\sqrt n，则复杂度为 O(m\sqrt n\log \sqrt n)=O(m\sqrt n\log n)。

// Problem: KQUERYO - K-Query Online
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP23776
// Memory Limit: 1 MB
// Time Limit: 200000 ms
// Start coding at 2024-01-16 21:00:36
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,q;
int bel[300005],val[300005],oval[300005],st[300005],ed[300005];
int B,C;
int qa(const int &l,const int &r,const int &k){
    if(l>r)return 0;
    int lB=bel[l],rB=bel[r],res=0;
    if(lB==rB){
        for(int i=l;i<=r;i++)res+=(oval[i]>k);
        return res;
    }
    for(int i=l;i<=ed[lB];i++)res+=(oval[i]>k);
    for(int i=lB+1;i<=rB-1;i++)res+=(val+ed[i]+1)-upper_bound(val+st[i],val+ed[i]+1,k);
    for(int i=st[rB];i<=r;i++)res+=(oval[i]>k);
    return res;
}
int l,r,k;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>val[i],oval[i]=val[i];
    B=sqrt(n),C=n/B;
    for(int i=1;i<=C;i++){
        st[i]=(i-1)*B+1;
        ed[i]=i*B;
        for(int j=st[i];j<=ed[i];j++)bel[j]=i;
        sort(val+st[i],val+ed[i]+1);
    }
    if(n%B){
        C++;
        st[C]=(C-1)*B+1;
        ed[C]=n;
        for(int j=st[C];j<=ed[C];j++)bel[j]=C;
        sort(val+st[C],val+n+1);
    }
    cin>>q;
    int lst=0;
    while(q--){
        cin>>l>>r>>k;
        l^=lst;
        r^=lst;
        k^=lst;
        l=max(l,1);
        r=min(r,n);
        cout<<(lst=qa(l,r,k))<<"\n";
    }
    return 0;
}

O(m\sqrt n)

对原序列离散化之后做值域分块（排序后在序列上序列分块），记录其在原数组里下标的桶，然后在桶内作前缀和。查询的时候先二分找到第一个比这个大的数的离散化后数据，然后访问每个块即可。取块长 B=\sqrt n，时间复杂度为 O((n+m)\sqrt n+m\log n)，空间复杂度为 O(n\sqrt n)。

// Problem: KQUERYO - K-Query Online
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP23776
// Memory Limit: 1 MB
// Time Limit: 200000 ms
// Start coding at 2024-01-17 15:09:06
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,q;
int bel[60005],st[60005],ed[60005];
int pre[301][60005],orp[60005];
pair<int,int> p[60005];
int B,C;
int qa(int pos,int l,int r){
    if(pos>n||r<l)return 0;
    int pB=bel[pos],res=0;
    for(int i=pos;i<=ed[pB];i++)res+=(p[i].second>=l&&p[i].second<=r);
    for(int i=pB+1;i<=C;i++)res+=pre[i][r]-pre[i][l-1];
    return res;
}
int k,l,r;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].first,p[i].second=i;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++)orp[i]=p[i].first;
    B=sqrt(n);
    C=n/B;
    for(int i=1;i<=C;i++){
        st[i]=(i-1)*B+1;
        ed[i]=i*B;
        for(int j=st[i];j<=ed[i];j++){
            bel[j]=i;
            pre[i][p[j].second]++;
        }
        for(int j=1;j<=n;j++)pre[i][j]+=pre[i][j-1];
    }
    if(n%B){
        C++;
        st[C]=(C-1)*B+1;
        ed[C]=n;
        for(int j=st[C];j<=ed[C];j++){
            bel[j]=C;
            pre[C][p[j].second]++;
        }
        for(int j=1;j<=n;j++)pre[C][j]+=pre[C][j-1];
    }
    cin>>q;
    int lst=0;
    while(q--){
        cin>>l>>r>>k;
        l^=lst;
        r^=lst;
        k^=lst;
        if(l<=1)l=1;
        if(r>=n)r=n;
        int pos=upper_bound(orp+1,orp+n+1,k)-orp;
        cout<<(lst=qa(pos,l,r))<<"\n";
    }
    return 0;
}

神秘的是，两份代码在 SPOJ 上跑出了一样的时间。