#include<bits/stdc++.h> #define MAXN 100005 #define MAXM 1000005 usingnamespace std; inlineintread(){ 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) inlinevoidupd(int pos,int val){ for (registerint i=pos;i<MAXN;i+=lowbit(i)){ c[i]+=val; } } inlineintqry(int pos){ int ans=0; for (registerint i=pos;i>0;i-=lowbit(i)){ ans+=c[i]; } return ans; } } usingnamespace BIT;
int pos[MAXN]; structQuery{ int l,r,a,b,id; }q[MAXM]; inlinebooloperator < (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]; intmain(){ int n=read(),m=read(); int Size=sqrt(n); for (registerint i=1;i<=n;++i){ a[i]=read(); pos[i]=(i-1)/Size+1; } for (registerint 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 (registerint 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 (registerint i=1;i<=m;++i){ printf("%d\n",Ans[i]); } }
这样的做法在洛古上面能过,但是GDOI上面过不了,为什么呢?
时间复杂度太高了,为O(nnlogn)
考虑我们莫队算法的特性。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
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);