Gty的二逼妹子序列 bzoj-3809
题目大意:给定一个n个正整数的序列,m次询问。每次询问一个区间$l_i$到$r_i$中,权值在$a_i$到$b_i$之间的数有多少个。
注释:$1\le n\le 10^5$,$1\le m\le 10^6$。
想法:说实话没想到分块和莫队。
考虑莫队如何处理旁区间:我们将值域分块。
每个块就存一下当前区间在这个块内有多少个值。特殊的是这个不是随时维护答案,是在区间刚好等于询问区间的时候处理。
莫队的时间复杂度是$O(n\sqrt{m})$;另外每次询问的时间复杂度是$O(\sqrt{n})$。
最后,附上丑陋的代码… …
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100001
using namespace std;
int n,m,c[N],blg[N],L[1050],R[1050],unit,t,ansblo[1050],h[N],ans[N*10];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
struct Node
{
int l,r,a,b,id;
}q[N*10];
bool cmp(const Node &x,const Node &y)
{
if(blg[x.l]!=blg[y.l]) return x.l<y.l;
return x.r<y.r;
}
int query(int l,int r)
{
int p=blg[l],q=blg[r],ans=0,i;
if(p==q)
{
for(i=l;i<=r;i++) if(h[i]) ans++;
return ans;
}
for(i=p+1;i<q;i++) ans+=ansblo[i];
for(i=l;i<=R[p];i++) if(h[i]) ans++;
for(i=L[q];i<=r;i++) if(h[i]) ans++;
return ans;
}
void del(int x)
{
h[x]--;
if(h[x]==0) ansblo[blg[x]]--;
}
void add(int x)
{
h[x]++;
if(h[x]==1) ansblo[blg[x]]++;
}
int main()
{
n=rd(); m=rd();
int i,j,unit=sqrt(n);
t=n/unit;
for(i=1;i<=t;i++)
{
L[i]=R[i-1]+1; R[i]=unit*i;
for(j=L[i];j<=R[i];j++)
{
c[j]=rd(); blg[j]=i;
}
}
if(R[t]!=n)
{
t++; L[t]=R[t-1]+1; R[t]=n;
for(i=L[t];i<=n;i++)
{
c[i]=rd(); blg[i]=t;
}
}
for(i=1;i<=m;i++)
{
q[i].l=rd(); q[i].r=rd(); q[i].a=rd(); q[i].b=rd();
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(i=1;i<=m;i++)
{
while(l<q[i].l) del(c[l]),l++;
while(r>q[i].r) del(c[r]),r--;
while(l>q[i].l) l--,add(c[l]);
while(r<q[i].r) r++,add(c[r]);
ans[q[i].id]=query(q[i].a,q[i].b);
}
for(i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
小结:莫队真可爱… …