[BZOJ3809]Gty的二逼妹子序列[莫队+分块]

题意

给出长度为 \(n\) 的序列，\(m\) 次询问，每次给出 \(l,r,a,b\) ，表示询问区间 \([l,r]\) 中，权值在 \([a,b]\) 范围的数的种类数。

\(n\leq 10^5,m\leq m\leq 10^6, a\leq b\leq n\)。

分析

• 直接莫队+树状数组的复杂度是 \(O(m\sqrt n\ logn)\)。

• 把树状数组改成分块，这样查询的时间是 \(O(\sqrt n)\) ，但是修改是 \(O(1)\) 的。

• 总时间复杂度为 \(O(m\sqrt n)\)。

当两种操作时间复杂度不平衡时或许有方法调节以降低复杂度

代码

#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int M=1e6 + 7,N=1e5 + 7;
int n,sz,m;
int bl[N],cnt[N],a[N],num[N];
int s[N],ans[M];
struct qs{
    int l,r,a,b,id;
    bool operator <(const qs &rhs)const{
        if(l/sz!=rhs.l/sz) return l/sz<rhs.l/sz;
        return r<rhs.r;
    }
}q[M];
int L(int x){return (x-1)*sz+1;}
int R(int x){return x*sz;}
void calc(int p,int f){
    if(f==1&&++cnt[ s[p] ]==1) {
        a[ s[p] ]+=f;
        num[ bl[ s[p] ] ]+=f;
    }
    if(f==-1&&--cnt[ s[p] ]==0){
        a[ s[p] ]+=f;
        num[ bl[ s[p] ] ]+=f;
    }
}
int query(int l,int r){
    int ans=0;
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;++i) ans+=a[i];
        return ans;
    }
    for(int b=bl[l]+1;b<bl[r];++b) ans+=num[b];
    for(int i=l;i<=R( bl[l] );++i) ans+=a[i];
    for(int i=L( bl[r] );i<=r;++i) ans+=a[i];
    return ans;
}
int main(){
    n=gi(),m=gi(),sz=sqrt(n);
    rep(i,1,n) s[i]=gi();
    rep(i,1,1e5) bl[i]=(i-1)/sz+1;
    rep(i,1,m) q[i].l=gi(),q[i].r=gi(),q[i].a=gi(),q[i].b=gi(),q[i].id=i;
    sort(q+1,q+1+m);
    int L=1,R=0;
    rep(i,1,m){
        while(R<q[i].r) calc(++R,1);
        while(L>q[i].l) calc(--L,1);
        while(R>q[i].r) calc(R--,-1);
        while(L<q[i].l) calc(L++,-1);
        ans[q[i].id]=query(q[i].a,q[i].b);
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

[BZOJ3809]Gty的二逼妹子序列[莫队+分块]

原文：https://www.cnblogs.com/yqgAKIOI/p/10066823.html