bzoj 3809 Gty的二逼妹子序列（莫队算法，块状链表）

【题意】

回答若干个询问，(l,r,a,b)：区间[l,r]内权值在[a,b]的数有多少[种]。

【思路】

考虑使用块状链表实现莫队算法中的插入与删除。

因为权值处于1..n之间，所以我们可以建一个基于权值的块状链表，每个块维护一个区间信息sum，表示权值在该块的数的种数。

这样插入与删除只需要O(1)的时间，查询需要O(sqrt(n))的时间，总的时间复杂度为O(n^1.5+qn^0.5)

【代码】

 #include<set>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long ll;

 const int N = 3e5+;

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 int n,m,B;

 int pos[N],sum[N],cnt[N],a[N],ans[N];

 struct Node

 {

     int id,l,r,a,b;

     bool operator < (const Node& rhs) const

     {

         return pos[l]<pos[rhs.l]||(pos[l]==pos[rhs.l]&&r<rhs.r);

     }

 } q[N];

 void upd(int x,int v)

 {

     cnt[x]+=v;

     if(v==&&cnt[x]==) sum[pos[x]]++;

     if(v==-&&cnt[x]==) sum[pos[x]]--;

 }

 int query(int l,int r)

 {

     int bl=pos[l],br=pos[r];

     int ans=;

     if(bl==br)

     {

         FOR(i,l,r) ans+=cnt[i]>;

         return ans;

     }

     FOR(i,bl+,br-) ans+=sum[i];

     bl=B*bl;

     br=B*(br-)+;

     FOR(i,l,bl) ans+=cnt[i]>;

     FOR(i,br,r) ans+=cnt[i]>;

     return ans;

 }

 int main()

 {

     n=read(),m=read();

     FOR(i,,n) a[i]=read();

     B=sqrt(n+0.5);

     FOR(i,,n) pos[i]=(i-)/B+;

     FOR(i,,m)

     {

         q[i].l=read(),q[i].r=read();

         q[i].a=read(),q[i].b=read();

         q[i].id=i;

     }

     sort(q+,q+m+);

     int l=,r=;

     FOR(i,,m)

     {

         while(l<q[i].l) upd(a[l++],-);

         while(l>q[i].l) upd(a[--l],);

         while(r<q[i].r) upd(a[++r],);

         while(r>q[i].r) upd(a[r--],-);

         ans[q[i].id]=query(q[i].a,q[i].b);

     }

     FOR(i,,m)

         printf("%d\n",ans[i]);

     return ;

 }