Steven_Meng's Blog

洛古

GDOI

首先，看见$“权值\in [a,b]的权值的种类数。”$这样的话就要想到莫队。

我们有一个比较显然的树状数组做法，每次加进一个数，如果没有出现，那么加进树状数组，删除也是类似，最后前缀和相减统计一下即可。

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],cnt[MAXN];
namespace BIT{
    int c[MAXN];
    #define lowbit(x) (x&-x)
    inline void upd(int pos,int val){
        for (register int i=pos;i<MAXN;i+=lowbit(i)){
            c[i]+=val;
        }
    }
    inline int qry(int pos){
        int ans=0;
        for (register int i=pos;i>0;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }
}
using namespace BIT;

int pos[MAXN];
struct Query{
    int l,r,a,b,id;
}q[MAXM];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int Ans[MAXM];
int main(){
    int n=read(),m=read();
    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
        while (l<q[i].l){
            if (--cnt[a[l]]==0) upd(a[l],-1);
            ++l;
        }
        while (l>q[i].l){
            --l;
            if (++cnt[a[l]]==1) upd(a[l],1);
        }
        while (r<q[i].r){
            ++r;
            if (++cnt[a[r]]==1) upd(a[r],1);
        }
        while (r>q[i].r){
            if (--cnt[a[r]]==0) upd(a[r],-1);
            --r;
        }
        Ans[q[i].id]=qry(q[i].b)-qry(q[i].a-1);
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}

这样的做法在洛古上面能过，但是$\rm GDOI$上面过不了，为什么呢？

时间复杂度太高了，为$O(n \sqrt n\log n)$

考虑我们莫队算法的特性。

while (l<q[i].l){
      if (--cnt[a[l]]==0) upd(a[l],-1);
      ++l;
}
while (l>q[i].l){
      --l;
      if (++cnt[a[l]]==1) upd(a[l],1);
}
while (r<q[i].r){
       ++r;
       if (++cnt[a[r]]==1) upd(a[r],1);
}
while (r>q[i].r){
       if (--cnt[a[r]]==0) upd(a[r],-1);
       --r;
}
Ans[q[i].id]=qry(q[i].b)-qry(q[i].a-1);

直观感受一下，一个循环里面，修改操作改了这么多次，但是查询只有一次。

所以我们适当降低修改操作的时间复杂度，提高查询操作的时间复杂度，可能可以达到提高程序效率的功能。

所以，我们使用分块，修改复杂度$O(1)$，查询复杂度$O(\sqrt n)$，就可以提高程序效率。

再仔细考虑一下，莫队整个算法也和分块密切相关，它的时间复杂度为$O(n \sqrt n)$，说明一次循环里面，$l,r$指针移动的次数是$O(\sqrt n)$级别，所以使用分块，前面修改复杂度为$O(1 \times \sqrt n)$，后面修改复杂度为$O(\sqrt n \times 1)$，合起来算一下，时间复杂度为$O(n \sqrt n)$，少了一个$\log $，是正确的。

总结：莫队和分块取长补短，可以达到降低时间复杂度的效果。

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],Size;
static int pos[MAXN],cnt[MAXN],val[MAXN];//块内所有数之和
namespace Divide_Into_Blocks{
    inline int Calc(int l,int r){
        int ans=0;
        for (register int i=l;i<=r;++i) ans+=cnt[i]>0;
        return ans;
    }
    inline int GetAns(int a,int b){
        int L=pos[a],R=pos[b];
        if (L==R) return Calc(a,b);
        int ans=0;
        for (register int i=L+1;i<=R-1;++i) ans+=val[i];
        return ans+Calc(a,L*Size)+Calc((R-1)*Size+1,b);
    }
}
using namespace Divide_Into_Blocks;
struct Query{
    int l,r,a,b,id;
}q[MAXM];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
inline void Add(int x){
    if (++cnt[x]==1) ++val[pos[x]];
}
inline void Del(int x){
    if (--cnt[x]==0) --val[pos[x]];
}
int Ans[MAXM];
int main(){
    int n=read(),m=read();
    Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
        while (l<q[i].l) Del(a[l++]);
        while (l>q[i].l) Add(a[--l]);
        while (r<q[i].r) Add(a[++r]);
        while (r>q[i].r) Del(a[r--]);
        Ans[q[i].id]=GetAns(q[i].a,q[i].b);
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}