BZOJ3809 Gty的二逼妹子序列 【莫队+分块】
同上题,BZOJ3236,简化了,只要求求数值的个数。
同样的做法,似乎我没加读入优化rank倒一……现在我做莫队题一块都是$O(\sqrt{\frac{n}{2}})$。
# include <stdio.h> # include <math.h> # include <algorithm> using namespace std; int n,m,t,left=1,right; int a[100010],cnt[100010],w[100010]; int g[10010]; int a2[1000010]; struct quest { int l,r,a,b,id; bool operator <(const quest &A) const{ if (w[l]==w[A.l]) return r<A.r; else return l<A.l; } }q[1000010]; inline void xy(int l,int r,int id) { if(w[l]==w[r]) { for (int i=l;i<=r;++i) if(cnt[i]) a2[id]++; } else { for (int i=w[l]*t-1;i>=l;--i) if(cnt[i]) a2[id]++; for (int i=w[r]*t-t;i<=r;++i) if(cnt[i]) a2[id]++; for (int i=w[l]+1;i<w[r];++i) a2[id]+=g[i]; } } inline void u(int x) { ++cnt[x]; if(cnt[x]==1) g[w[x]]++; } inline void v(int x) { --cnt[x]; if(cnt[x]==0) g[w[x]]--; } int main() { scanf("%d%d",&n,&m); t=sqrt(n/2); for (int i=1;i<=n;++i) scanf("%d",&a[i]),w[i]=i/t+1; for (int i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i; sort(q+1,q+m+1); for (int i=1;i<=m;++i) { while(right<q[i].r) u(a[++right]); while(left<q[i].l) v(a[left++]); while(right>q[i].r) v(a[right--]); while(left>q[i].l) u(a[--left]); xy(q[i].a,q[i].b,q[i].id); } for (int i=1;i<=m;++i) printf("%d\n",a2[i]); }