想想查询一个区间的众数时会出现什么情况。
一个区间包含三种块，左端点块（块 $1$ )，右端点块（块 $2$ ）和其它在区间内的块（块 $3$ ）。
很显然的是，在块 $2$ 中不是众数的数，在经过块 $1$ 和块 $3$ 的补充后，可以变成众数。
所以区间众数有三种可能：块 $1$ 、 $3$ 中出现的数，及块 $2$ 的众数。

块 $2$ 的信息显然需要快速查询。
于是我们要维护几个连续块的众数，及各数字出现的次数。
这些东西都可以在 $O(n\sqrt n)$ 的时间内预处理出来。（枚举从哪一个块开始）

然后在询问中，暴力统计块 $1$ 和块 $3$ 中出现的数的出现次数即可。这个最高复杂度 $O(2\sqrt n)$ 。

于是这个问题在 $O(n\sqrt n)$ 时间复杂度内得到了解决。

https://new.loj.ac/submission/207574

考试题

2018.9.20街灯

给一个数列 $\{a\}$ ，每次给出 $l,r,p,v$ ，询问一个区间内模 $p$ 等于 $v$ 的数有多少个。

$n\leq10^5,q\leq10^5,p\leq10^9,a_i\leq10^4$

这个显然只能分块做。但是和上面的不太一样。
实际上 $p\leq10^4$ 。
我们先预处理出 $p\leq100$ 时所有答案（以前缀和的形式）。
然后处理出数字出现次数的前缀和。
每次询问， $p\leq100$ 直接 $O(1)$ 回答，否则暴力枚举 $i*p+v$ 来统计答案，这里复杂度只有 $O(\sqrt n)$ （所以分块就是用来优化暴力的）。
答案都是前缀和相减的形式。

时间复杂度 $O(n\sqrt p)$ 。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define pb(a) push_back(a)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int A[N],n,m,f[105][105],t[10005];
struct que{int l,r,p,v,ans;}a[N];
vector<int>q[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();
  fp(i,1,n) A[i]=gi();
  fp(i,1,m)
    {
      a[i].l=gi();a[i].r=gi();a[i].p=gi();a[i].v=gi();a[i].ans=0;
      q[a[i].l-1].pb(i);q[a[i].r].pb(i);
    }
  fp(i,1,n)
    {
      ++t[A[i]];
      fp(j,1,100) ++f[j][A[i]%j];
      for(re int j=0;j<q[i].size();j++)
    {
      re int id=q[i][j],gu=(i==a[id].r)?1:-1,p=a[id].p,v=a[id].v;
      if(p<=100) a[id].ans+=gu*f[p][v];
      else
        for(re int i=0;i*p+v<=10000;i++)
          a[id].ans+=gu*t[i*p+v];
    }
    }
  fp(i,1,m) printf("%d\n",a[i].ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

专题总结(分块)

思想

模板

考试题

2018.9.20街灯

内容目录