bzoj 3809 Gty的二逼妹子序列——莫队+分块

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3809

容易想到树状数组维护值域。但修改和查询都是 log 太慢。

考虑有 nsqrt(n) 个修改、m个查询，所以给查询 sqrt(n) ，给修改 O(1) 。对值域分块即可。（msqrt(n)也能过？）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1e5+,M=1e6+,K=;

int n,m,a[N],base,bh[N],cnt[N],sm[K],ans[M];

struct Ques{

  int l,r,a,b,bh;

}q[M];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

bool cmp(Ques u,Ques v){return bh[u.l]==bh[v.l]?u.r<v.r:bh[u.l]<bh[v.l];}

void add(int x)

{

  if(!cnt[x])sm[bh[x]]++; cnt[x]++;

}

void del(int x)

{

  cnt[x]--; if(!cnt[x])sm[bh[x]]--;

}

int query(int l,int r)

{

  int ret=;

  if(bh[r]-bh[l]<=)

    {

      for(int i=l;i<=r;i++)if(cnt[i])ret++;

      return ret;

    }

  for(int i=bh[l]+;i<bh[r];i++) ret+=sm[i];

  int L=base*bh[l],R=base*(bh[r]-);

  for(int i=l;i<=L;i++)if(cnt[i])ret++;

  for(int i=R+;i<=r;i++)if(cnt[i])ret++;

  return ret;

}

int main()

{

  n=rdn(); m=rdn(); base=sqrt(n);

  for(int i=;i<=n;i++) a[i]=rdn(),bh[i]=(i-)/base+;

  for(int i=;i<=m;i++)

    q[i].l=rdn(),q[i].r=rdn(),q[i].a=rdn(),q[i].b=rdn(),q[i].bh=i;

  sort(q+,q+m+,cmp);

  int L=,R=;

  for(int i=;i<=m;i++)

    {

      int l=q[i].l,r=q[i].r;

      while(L>l)add(a[--L]);

      while(R<r)add(a[++R]);

      while(L<l)del(a[L++]);

      while(R>r)del(a[R--]);

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

    }

  for(int i=;i<=m;i++)printf("%d\n",ans[i]);

  return ;

}