前言举个栗子
JZOJ1902
神奇的分块Whycode JZOJ1942
带修莫队code 后记
前言
RT，莫队算法的真名应该叫做 一个优雅的暴力（引自Alan_Cty）
举个栗子
JZOJ1902
Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
Input 输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。 接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。 再接下来M行，每行两个正整数L，R表示一个询问。
Output 输出文件包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
Sample Input 6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6
Sample Output 2/5 0/1 1/1 4/15
Data Constraint
Hint 【样例解释】 询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。 询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。 询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。 注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据范围】 30%的数据中 N,M ≤ 5000； 60%的数据中 N,M ≤ 25000； 100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
很显然，线段树之类的不能满足题目要求的乱搞。 直接暴力的话时间就是
O(N2)
思考一种更加优(bao)美 (li)的算法， 假设已知当前询问的答案，能否推向下一个询问？ 显然可以。公式什么的自己想 可以通过
O(1)
的时间来维护序列&计算答案。
只不过这样暴力去搞的话时间是
O(2N2)
(两个指针) 爆炸*2
所以我们的目标就是让指针移动次数尽量小的情况下，安排好处理询问的顺序。 当然可以直接平面上的曼哈顿距离最小生成树，不过时间是
O(N2)
，这样就失去了莫队的意义。 不过有一种神奇的曼哈顿距离最小生成树，时间是
O(NlogN)
的，十分玄学~~
神奇的分块
当然，如果要用上面的玄学操作，莫队算法就不可能这么普及。 考虑用分块大法。 对于询问
[l,r]
,按l所在的块数为第一关键字，r为第二关键字排序。 这样搞不一定能保证距离最小，但是能在距离相对小的情况下时间也相对小。
Why
因为分块避免了以下的情况： 暴力排序的话，要这样走： 明显浪费时间。
分块的话，要这样走（灰线为分界线）：
少走多少不言而喻。 还有，分块最好是分成大小为
√N
的一块。 时间复杂度是
O(N√N)
code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;
long long a[
50001];
long long b[
50001];
long long c[
50001];
long long d[
50001];
long long fk[
50001];
long long ans[
50001];
long long ans2[
50001];
long long num[
50001];
long long n,m,i,j,k,
sum,l,r;
float sq;
long long gcd(
long long x,
long long y)
{
long long r;
if (x==
0)
return y;
r=x%y;
while (r)
{
x=y;
y=r;
r=x%y;
}
return y;
}
void qsort(
long long l,
long long r)
{
long long i,j,k,mid,mid2;
i=l;
j=r;
mid=fk[(l+r)/
2];
mid2=c[(l+r)/
2];
while (i<=j)
{
while ((fk[i]<mid)||((fk[i]==mid)&&(c[i]<mid2))) i++;
while ((fk[j]>mid)||((fk[j]==mid)&&(c[j]>mid2))) j--;
if (i<=j)
{
k=fk[i];
fk[i]=fk[j];
fk[j]=k;
k=b[i];
b[i]=b[j];
b[j]=k;
k=c[i];
c[i]=c[j];
c[j]=k;
k=d[i];
d[i]=d[j];
d[j]=k;
i++;
j--;
}
}
if (l<j)
qsort(l,j);
if (i<r)
qsort(i,r);
return;
}
int main()
{
scanf(
"%d%d",&n,&m);
sq=sqrt(n);
fo(i,
1,n)
scanf(
"%d",&a[i]);
fo(i,
1,m)
{
scanf(
"%d%d",&b[i],&c[i]);
d[i]=i;
fk[i]=floor(b[i]/sq);
}
qsort(
1,m);
l=b[
1];
r=c[
1];
sum=
0;
fo(i,l,r)
{
if (num[a[i]]>
1)
sum-=num[a[i]]*(num[a[i]]-
1);
num[a[i]]++;
if (num[a[i]]>
1)
sum+=num[a[i]]*(num[a[i]]-
1);
}
ans[d[
1]]=
sum/
2;
ans2[d[
1]]=r-l+
1;
ans2[d[
1]]*=(ans2[d[
1]]-
1);
ans2[d[
1]]/=
2;
j=gcd(ans[d[
1]],ans2[d[
1]]);
ans[d[
1]]/=j;
ans2[d[
1]]/=j;
fo(i,
2,m)
{
if (l>b[i])
{
fd(j,l-
1,b[i])
{
if (num[a[j]]>
1)
sum-=num[a[j]]*(num[a[j]]-
1);
num[a[j]]++;
if (num[a[j]]>
1)
sum+=num[a[j]]*(num[a[j]]-
1);
}
l=b[i];
}
if (r<c[i])
{
fo(j,r+
1,c[i])
{
if (num[a[j]]>
1)
sum-=num[a[j]]*(num[a[j]]-
1);
num[a[j]]++;
if (num[a[j]]>
1)
sum+=num[a[j]]*(num[a[j]]-
1);
}
r=c[i];
}
if (l<b[i])
{
fo(j,l,b[i]-
1)
{
if (num[a[j]]>
1)
sum-=num[a[j]]*(num[a[j]]-
1);
num[a[j]]--;
if (num[a[j]]>
1)
sum+=num[a[j]]*(num[a[j]]-
1);
}
l=b[i];
}
if (r>c[i])
{
fd(j,r,c[i]+
1)
{
if (num[a[j]]>
1)
sum-=num[a[j]]*(num[a[j]]-
1);
num[a[j]]--;
if (num[a[j]]>
1)
sum+=num[a[j]]*(num[a[j]]-
1);
}
r=c[i];
}
ans[d[i]]=
sum/
2;
ans2[d[i]]=c[i]-b[i]+
1;
ans2[d[i]]*=(ans2[d[i]]-
1);
ans2[d[i]]/=
2;
j=gcd(ans[d[i]],ans2[d[i]]);
ans[d[i]]/=j;
ans2[d[i]]/=j;
}
fo(i,
1,m)
printf(
"%d%c%d\n",ans[i],
'/',ans2[i]);
}
JZOJ1942
Description 墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。 为了满足墨墨的要求，你知道你需要干什么了吗？
Input 第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。 第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。 第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。 Output 对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
Sample Input 6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6 Sample Output 4 4 3 4
Data Constraint
Hint 【数据规模】 对于40%数据，只包含第一类操作（无修改操作），且。 除此之外的20%的数据，N，M≤1000 对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
带修莫队
顾名思义，就是带修改功能的莫队算法。 当然肯定是离线的啊~ 按照修改次数为第三关键字排序，每次先修改，再更新，如果在当前区间范围内的要修改维护的颜色序列。 其实很简单~~
时间复杂度十分玄学，是O(N^(5/3))。 每块大小最好为N^(2/3)。 证明看各种大牛的博客。
code
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cmath>
#define fo(
a,b,c) for (
a=b
#define fd(
a,b,c) for (
a=b
using namespace std
int n,m,i,j,k,n1,n2,l,r,s,ans
int
a[
10001][
5]
int b[
10001]
int bb[
10001]
int cg[
10001][
3]
int num[
1000001]
int anss[
10001]
char ch
double sq
string sssss
void qsort(int l,int r)
{
int i,j,k,mid1,mid2,mid3
i=l
j=r
mid1=
a[(l+r)/
2][
3]
mid2=
a[(l+r)/
2][
1]
mid3=
a[(l+r)/
2][
2]
while (i<=j)
{
while ((
a[i][
3]<mid1)||((
a[i][
3]==mid1)&&(
a[i][
1]<mid2))||((
a[i][
3]==mid1)&&(
a[i][
1]==mid2)&&(
a[i][
2]<mid3))) i++
while ((
a[j][
3]>mid1)||((
a[j][
3]==mid1)&&(
a[j][
1]>mid2))||((
a[j][
3]==mid1)&&(
a[j][
1]==mid2)&&(
a[j][
2]>mid3))) j--
if (i<=j)
{
k=
a[i][
0]
a[i][
0]=
a[j][
0]
a[j][
0]=k
k=
a[i][
1]
a[i][
1]=
a[j][
1]
a[j][
1]=k
k=
a[i][
2]
a[i][
2]=
a[j][
2]
a[j][
2]=k
k=
a[i][
3]
a[i][
3]=
a[j][
3]
a[j][
3]=k
k=
a[i][
4]
a[i][
4]=
a[j][
4]
a[j][
4]=k
i++
j--
}
}
if (l<j)
qsort(l,j)
if (i<r)
qsort(i,r)
return
}
int main()
{
cin>>n>>m
fo(i,
1,n)
{
cin>>b[i]
bb[i]=b[i]
}
sq=sqrt(n)
fo(i,
1,m)
{
cin>>ch>>j>>k
if (ch=='Q')
{
n1++
a[n1][
0]=j
a[n1][
1]=k
a[n1][
2]=n2
a[n1][
3]=floor(j/sq)
a[n1][
4]=n1
}
else
{
n2++
cg[n2][
0]=j
cg[n2][
1]=k
cg[n2][
2]=b[j]
b[j]=k
}
}
fo(i,
1,n)
b[i]=bb[i]
qsort(
1,n1)
l=
0
r=
0
s=
0
ans=
0
fo(i,
1,n1)
{
if (s<
a[i][
2])
{
fo(j,s+
1,
a[i][
2])
{
if ((l<=cg[j][
0]) && (cg[j][
0]<=r))
{
num[b[cg[j][
0]]]--
if (num[cg[j][
2]]==
0)
ans--
num[cg[j][
1]]++
if (num[cg[j][
1]]==
1)
ans++
}
b[cg[j][
0]]=cg[j][
1]
}
s=
a[i][
2]
}
else
if (s>
a[i][
2])
{
fd(j,s,
a[i][
2]+
1)
{
if ((l<=cg[j][
0]) && (cg[j][
0]<=r))
{
num[b[cg[j][
0]]]--
if (num[cg[j][
1]]==
0)
ans--
num[cg[j][
2]]++
if (num[cg[j][
2]]==
1)
ans++
}
b[cg[j][
0]]=cg[j][
2]
}
s=
a[i][
2]
}
if (l>
a[i][
0])
{
fd(j,l-
1,
a[i][
0])
{
num[b[j]]++
if (num[b[j]]==
1)
ans++
}
l=
a[i][
0]
}
if (r<
a[i][
1])
{
fo(j,r+
1,
a[i][
1])
{
num[b[j]]++
if (num[b[j]]==
1)
ans++
}
r=
a[i][
1]
}
if (l<
a[i][
0])
{
fo(j,l,
a[i][
0]-
1)
{
num[b[j]]--
if (num[b[j]]==
0)
ans--
}
l=
a[i][
0]
}
if (r>
a[i][
1])
{
fd(j,r,
a[i][
1]+
1)
{
num[b[j]]--
if (num[b[j]]==
0)
ans--
}
r=
a[i][
1]
}
anss[
a[i][
4]]=ans
}
fo(i,
1,n1)
cout<<anss[i]<<endl
}
后记
莫队算法是解决离线问题的利器，对于在线问题就gg了。 关于带修莫队的代码有些错误，与2017年9月20日20点46分修正。 因为可能会出现多次修改同一个点同一个值的情况， 在JZOJ4594. 【NOIP2016模拟7.8】Dynamic len上有体现。 （大致和本题相同）
参考资料： 莫队算法 支(zi)持(ci)修改的莫队算法 莫队算法学习小记
