平板做网站服务器,企业网站做seo,桂林有什么好玩的地方,电商网站设计页面设计曼哈顿距离最小生成树与莫队算法#xff08;总结#xff09; 1 曼哈顿距离最小生成树 曼哈顿距离最小生成树问题可以简述如下#xff1a; 给定二维平面上的N个点#xff0c;在两点之间连边的代价为其曼哈顿距离#xff0c;求使所有点连通的最小代价。 朴素的算法可以用O(N… 曼哈顿距离最小生成树与莫队算法总结 1 曼哈顿距离最小生成树 曼哈顿距离最小生成树问题可以简述如下 给定二维平面上的N个点在两点之间连边的代价为其曼哈顿距离求使所有点连通的最小代价。 朴素的算法可以用O(N2)的Prim或者处理出所有边做Kruskal但在这里总边数有O(N2)条所以Kruskal的复杂度变成了O(N2logN)。 但是事实上真正有用的边远没有O(N2)条。我们考虑每个点会和其他一些什么样的点连边。可以得出这样一个结论以一个点为原点建立直角坐标系在每45度内只会向距离该点最近的一个点连边。 这个结论可以证明如下假设我们以点A为原点建系考虑在y轴向右45度区域内的任意两点B(x1,y1)和C(x2,y2)不妨设|AB|≤|AC|这里的距离为曼哈顿距离如下图 |AB|x1y1|AC|x2y2|BC||x1-x2||y1-y2|。而由于B和C都在y轴向右45度的区域内有y-x0且x0。下面我们分情况讨论 1. x1x2且y1y2。这与|AB|≤|AC|矛盾 2. x1≤x2且y1y2。此时|BC|x2-x1y1-y2|AC|-|BC|x2y2-x2x1-y1y2x1-y12*y2。由前面各种关系可得y1y2x2x1。假设|AC||BC|即y12*y2x1那么|AB|x1y12*x12*y2|AC|x2y22*y2|AB|与前提矛盾故|AC|≥|BC| 3. x1x2且y1≤y2。与2同理 4. x1≤x2且y1≤y2。此时显然有|AB||BC||AC|即有|AC||BC|。 综上有|AC|≥|BC|也即在这个区域内只需选择距离A最近的点向A连边。 这种连边方式可以保证边数是O(N)的那么如果能高效处理出这些边就可以用Kruskal在O(NlogN)的时间内解决问题。下面我们就考虑怎样高效处理边。 我们只需考虑在一块区域内的点其他区域内的点可以通过坐标变换“移动”到这个区域内。为了方便处理我们考虑在y轴向右45度的区域。在某个点A(x0,y0)的这个区域内的点B(x1,y1)满足x1≥x0且y1-x1y0-x0。这里对于边界我们只取一边但是操作中两边都取也无所谓。那么|AB|y1-y0x1-x0(x1y1)-(x0y0)。在A的区域内距离A最近的点也即满足条件的点中xy最小的点。因此我们可以将所有点按x坐标排序再按y-x离散用线段树或者树状数组维护大于当前点的y-x的最小的xy对应的点。时间复杂度O(NlogN)。 至于坐标变换一个比较好处理的方法是第一次直接做第二次沿直线yx翻转即交换x和y坐标第三次沿直线x0翻转即将x坐标取相反数第四次再沿直线yx翻转。注意只需要做4次因为边是双向的。 至此整个问题就可以在O(NlogN)的复杂度内解决了。 2 莫队算法 据说这个算法是莫涛提出的Orz但是在网上到处都搜不到相关资料最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题清橙A1206《小Z的袜子》就是莫队出的题 给定一个长为N的序列每个元素的值是其颜色。有M次询问每次询问从一个区间中随机选取两个元素同色的概率。 一次询问[l,r]的答案即其中是区间中第i中颜色的个数。显然暴力是O(NM)的而且一般的区间问题的思路似乎不适用。 我们先考虑一个简化的问题所有的查询区间的左端点都是1。那么我们可以按右端点排序假设已经处理出了[1,r]的答案考虑转移到[1,rk]即添加k个元素这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度不考虑排序就是O(N)。 那么如果是从[l,r]转移到[l’,r’]呢复杂度即O(|r’-r||l’-l|)也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点求曼哈顿距离最小生成树再按照生成树的顺序做就可以最小化区间之间转移的复杂度。可以证明我不会证……似乎莫队的论文里有这样做的复杂度是O(N^1.5)的。问题也就得到了解决。 【BZOJ2038】小Z的袜子 传送门 写在前面莫队竟如此暴力…… 思路当初我对这个题的第一感觉——这个区间问题可以用线段树或者树状数组答案当然是不能于是我就去简单学了下莫队算法。在我看来莫队分块版不是二维曼哈顿距离什么什么最小生成树就是分块排序优化暴力查找减少查找区间之间的覆盖长度从而优化时间复杂度有一种说法很精彩 如果我们已知[l,r]的答案能在O(1)时间得到[l1,r]的答案以及[l,r-1]的答案即可使用莫队算法。时间复杂度为O(n^1.5)。如果只能在logn的时间移动区间则时间复杂度是O(n^1.5*log n)。 其实就是找一个数据结构支持插入、删除时维护当前答案。 这道题的话我们很容易用数组来实现做到O(1)的从[l,r]转移到[l,r1]与[l1,r]。 那么莫队算法怎么做呢以下都是在转移为O(1)的基础下讨论的时间复杂度。另外由于n与m同阶就统一写n。 如果已知[l,r]的答案要求[l’,r’]的答案我们很容易通过|l – l’||r – r’|次转移内求得。 对于它的时间复杂度分析 将n个数分成sqrt(n)块。 按区间排序以左端点所在块内为第一关键字右端点为第二关键字进行排序也就是以(pos [l]r)排序 然后按这个排序直接暴力复杂度分析是这样的 1、i与i1在同一块内r单调递增所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。 2、i与i1跨越一块r最多变化n由于有n^0.5块所以这一部分时间复杂度是n^1.5 3、i与i1在同一块内时变化不超过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−L1)∗(R−L)) 简化可得 ans(Σ(sum(color[i])2)−(R−L1))/((R−L1)∗(R−L)) 其中sum(color[i])指第i种颜色在[L,R]中出现的次数 那么我们现在求出各个询问区间中sum(color[i])2就行了具体实现方法参照代码 注意 1.当一种颜色数量ci增加1时我们可以看出ansans−ci2(ci1)2简化可得ansans(ci∗21)同样减少1时ansans−ci2(ci−1)2简化得ansans(ci∗2−1)这样做的好处是减少乘法且可用位运算优化常数然而并没有什么卵用 2.极限数据50000*50000如果不用longlong会教你做人←_← 代码 1 #includebits/stdc.h2 #define LL long long3 using namespace std;4 int n,m,last_l1,last_r;5 LL ans,p;6 int color[50010],block[50010];7 LL sum[50010];8 struct os9 {
10 LL part,l,r,nume,deno;//nume指分子deno指分母
11 }q[50010];
12 int cmp1(os xx,os yy)
13 {
14 if (block[xx.l]block[yy.l]) return 1;
15 if (block[xx.l]block[yy.l]) return 0;
16 return xx.ryy.r;
17 }
18 int cmp2(os xx,os yy){return xx.partyy.part;}
19 inline LL gcd(LL x,LL y)
20 {
21 if (!y) return x;
22 return gcd(y,x%y);
23 }
24 main()
25 {
26 scanf(%d%d,n,m);
27 for (int i1;in;i) scanf(%d,color[i]);
28 block[0]sqrt(n);
29 for (int i1;in;i)
30 block[i](i-1)/block[0]1;
31 for (int i1;im;i)
32 scanf(%d%d,q[i].l,q[i].r),
33 q[i].parti;
34 sort(q1,qm1,cmp1);
35
36 for (int i1;im;i)
37 {
38 q[i].deno(q[i].r-q[i].l1)*(q[i].r-q[i].l);
39 if (last_rq[i].r)
40 {
41 for (int jlast_r1;jq[i].r;j)
42 ans((sum[color[j]]1)1),
43 sum[color[j]];
44 }
45 if (last_rq[i].r)
46 {
47 for (int jlast_r;jq[i].r;j--)
48 ans-((sum[color[j]]1)-1),
49 sum[color[j]]--;
50 }
51 if (last_lq[i].l)
52 {
53 for (int jlast_l-1;jq[i].l;j--)
54 ans((sum[color[j]]1)1),
55 sum[color[j]];
56 }
57 if (last_lq[i].l)
58 {
59 for (int jlast_l;jq[i].l;j)
60 ans-((sum[color[j]]1)-1),
61 sum[color[j]]--;
62 }
63 q[i].numeans-(q[i].r-q[i].l1);
64 last_lq[i].l;
65 last_rq[i].r;
66 }
67 sort(q1,qm1,cmp2);
68 for (int i1;im;i)
69 {
70 if (!q[i].nume){printf(0/1\n);continue;}
71 pgcd(q[i].nume,q[i].deno);
72 printf(%lld/%lld\n,q[i].nume/p,q[i].deno/p);
73 }
74 } 转载于:https://www.cnblogs.com/Renyi-Fan/p/8137948.html
