【BZOJ2038】小Z的袜子 莫队居然如此暴力！！
版权声明： https://blog.csdn.net/xym_CSDN/article/details/50889293 </div>
<div id="content_views" class="markdown_views">
<!-- flowchart 箭头图标 勿删 -->
<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg>
<p><a href="http://www.lydsy.com/JudgeOnline/problem.php?id=2038" rel="nofollow" target="_blank">传送门</a> <br>
写在前面：莫队竟如此暴力……
思路：当初我对这个题的第一感觉——这个区间问题可以用线段树或者树状数组？答案当然是不能，于是我就去简单学了下莫队算法。在我看来，莫队（分块版，不是二维曼哈顿距离什么什么最小生成树）就是分块排序优化暴力查找，减少查找区间之间的覆盖长度，从而优化时间复杂度，有一种说法很精彩
如果我们已知[l,r]的答案，能在O(1)时间得到[l+1,r]的答案以及[l,r-1]的答案，即可使用莫队算法。时间复杂度为O(n^1.5)。如果只能在logn的时间移动区间，则时间复杂度是O(n^1.5*log
n)。 其实就是找一个数据结构支持插入、删除时维护当前答案。
这道题的话我们很容易用数组来实现，做到O(1)的从[l,r]转移到[l,r+1]与[l+1,r]。
那么莫队算法怎么做呢？以下都是在转移为O(1)的基础下讨论的时间复杂度。另外由于n与m同阶，就统一写n。
如果已知[l,r]的答案，要求[l’,r’]的答案，我们很容易通过|l – l’|+|r – r’|次转移内求得。
对于它的时间复杂度分析
将n个数分成sqrt(n)块。 按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序，也就是以(pos [l]，r)排序
然后按这个排序直接暴力，复杂度分析是这样的：
1、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
2、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5
3、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过n^0.5，忽略*2。由于有n个数，所以时间复杂度是n^1.5
于是就是O(n^1.5)了
这道题是比较模板的莫队分块了，对于一个区间询问[L,R]，我们要求的ans是
ans=(Σsum(color[i])−1)∗sum(color[i])/2)/((R−L+1)∗(R−L))ans=(Σsum(color[i])−1)∗sum(color[i])/2)/((R−L+1)∗(R−L))，这样做的好处是减少乘法且可用位运算，优化常数（然而并没有什么卵用）
2.极限数据50000*50000如果不用longlong会教你做人←_←
代码：
#include"bits/stdc++.h"
#define LL long long
using namespace std;
int n,m,last_l=1,last_r;
LL ans,p;
int color[50010],block[50010];
LL sum[50010];
struct os
{
LL part,l,r,nume,deno;//nume指分子，deno指分母
}q[50010];
int cmp1(os xx,os yy)
{
if (block[xx.l]<block[yy.l]) return 1;
if (block[xx.l]>block[yy.l]) return 0;
return xx.r<yy.r;
}
int cmp2(os xx,os yy){return xx.part<yy.part;}
inline LL gcd(LL x,LL y)
{
if (!y) return x;
return gcd(y,x%y);
}
main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&color[i]);
block[0]=sqrt(n);
for (int i=1;i<=n;i++)
block[i]=(i-1)/block[0]+1;
for (int i=1;i<=m;i++)
scanf("%d%d",&q[i].l,&q[i].r),
q[i].part=i;
sort(q+1,q+m+1,cmp1);
for (int i=1;i<=m;i++)
{
q[i].deno=(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
if (last_r<q[i].r)
{
for (int j=last_r+1;j<=q[i].r;j++)
ans+=((sum[color[j]]<<1)+1),
sum[color[j]]++;
}
if (last_r>q[i].r)
{
for (int j=last_r;j>q[i].r;j--)
ans-=((sum[color[j]]<<1)-1),
sum[color[j]]--;
}
if (last_l>q[i].l)
{
for (int j=last_l-1;j>=q[i].l;j--)
ans+=((sum[color[j]]<<1)+1),
sum[color[j]]++;
}
if (last_l<q[i].l)
{
for (int j=last_l;j<q[i].l;j++)
ans-=((sum[color[j]]<<1)-1),
sum[color[j]]--;
}
q[i].nume=ans-(q[i].r-q[i].l+1);
last_l=q[i].l;
last_r=q[i].r;
}
sort(q+1,q+m+1,cmp2);
for (int i=1;i<=m;i++)
{
if (!q[i].nume){printf("0/1\n");continue;}
p=gcd(q[i].nume,q[i].deno);
printf("%lld/%lld\n",q[i].nume/p,q[i].deno/p);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
<link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-7b4cdcb592.css" rel="stylesheet">
</div>
