莫队算法

PhoenixGS 2017年9月27日2017年12月22日莫队算法, 算法介绍 8 Comments

莫队算法

有一个序列，且有一些区间询问，便可以考虑用神奇的莫队算法！

实现

莫队是一种离线算法，用到了分块的思想，将序列分块，设每个块的长度为 $S$ 。在输入所有询问之后，按 $(\lfloor\frac{l}{S}\rfloor,r)$ 二元组从小到大排序，之后按顺序暴力移动左右端点并统计答案。

时间复杂度

设序列的长度为 $n$ ，询问个数为 $m$ ，从 $[l,r]$ 扩展到 $[l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]$ 的时间复杂度为 $O(f(n))$ ，于是从 $(l1, r1)$ 转移到 $(l2, r2)$ 的时间为 $O((|l1 - l2| + |r1 - r2|) * f(n))$ 对于每一个块中的所有询问，最多使 $r$ 移动 $n$ ，每个询问最多使 $l$ 移动 $S$ ，一共有 $\frac{n}{S}$ ，相邻两个块转移的时间复杂度为 $O(n * f(n))$ ，所以总时间复杂度为 $O((\frac{n ^ 2}{S}+mS+\frac{n ^ 2}{S}) * f(n))$ ，当 $n, m$ 同阶时，使 $S = \sqrt{n}$ ，总时间复杂度即为 $O(n\sqrt{n} * f(n))$

模板

bool quescomp(T x, T y)
{
    if (knum[x.l] == knum[y.l])
    {
        return x.r < y.r;
    }
    return knum[x.l] < knum[y.l];
}

1

2

3

4

5

6

7

8

bool quescomp(T x, T y)

{

if (knum[x.l] == knum[y.l])

{

return x.r < y.r;

}

return knum[x.l] < knum[y.l];

}

int knumber = (int)sqrt(n);
for (int i = 1; i <= n; i++)
{
    knum[i] = (i - 1) / knumber + 1;
}
std::sort(ques + 1, ques + T + 1, quescomp);
for (int i = 1, l = 1, r = 0; i <= Q; i++)
{
    for (; l < ques[i].l; l++)
    {
        update(l, -1);
    }
    for (; l > ques[i].l; l--)
    {
        update(l - 1, 1);
    }
    for (; r < ques[i].r; r++)
    {
        update(r + 1, 1);
    }
    for (; r > ques[i].r; r--)
    {
        update(r, -1);
    }
    //calc ans
}

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

int knumber = (int)sqrt(n);

for (int i = 1; i <= n; i++)

{

knum[i] = (i - 1) / knumber + 1;

}

std::sort(ques + 1, ques + T + 1, quescomp);

for (int i = 1, l = 1, r = 0; i <= Q; i++)

{

for (; l < ques[i].l; l++)

{

update(l, -1);

}

for (; l > ques[i].l; l--)

{

update(l - 1, 1);

}

for (; r < ques[i].r; r++)

{

update(r + 1, 1);

}

for (; r > ques[i].r; r--)

{

update(r, -1);

}

//calc ans

}

莫队算法

Tagged on: 算法介绍莫队算法

8 thoughts on “莫队算法”

Junqi Huang
2017年12月7日 at 下午12:13
Permalink

%%%
膜拜FKC大佬
Reply
aspillic
2017年12月12日 at 上午9:29
Permalink

Nach meiner Meinung lassen Sie den Fehler zu. Geben Sie wir werden es besprechen. Schreiben Sie mir in PM, wir werden umgehen.
http://drstore.top/

http://letsbeabestshop.tumblr.com/
http://longviberi.tumblr.com/
https://twitter.com/tonyjfrost1910

http://toy-shop.top/
http://orshop.top/
http://onews.life/
Reply
aspillic
2017年12月13日 at 下午3:30
Permalink

Hello there I am so excited I found your website, I really found you by accident, while I was searching on Askjeeve for something else, Anyhow I am here now and would just like to say thanks for a incredible post and a all round thrilling blog (I also love the theme/design), I dont have time to read through it all at the moment but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the fantastic work.
http://www.milfsuck.top/s/old+young+piss
http://newbp.win/results/orgasm+compliation
http://www.easynaked.top/s/lezdom+tits
http://newbp.win/results/wide+open+legs
http://www.nbp.pw/results/feet+sweat

http://www.sexybang.top/
http://www.cumsucking.top/
http://htube.hordo.win/
http://newbp.win/
http://bestporn.buron.pw/

http://momsex.hordo.win/
http://newbp.win/
http://www.bangwhore.top/
Reply
aspillic
2017年12月15日 at 上午4:47
Permalink

Diese ausgezeichnete Idee fГ¤llt gerade Гјbrigens
http://www.easynaked.top/s/natalie+masturbation
http://www.bangwhore.top/s/blonde+cosplay
http://www.whorebutt.top/gallery/3330/she-thinks-nobody-can-see-her-masturbating-in-the-field.html

http://www.cumsucking.top/
http://tons.hordo.win/
http://babes-porn.buron.pw/

http://babes-porn.buron.pw/
http://amateur.buron.pw/
Reply
aspillic
2017年12月17日 at 上午5:47
Permalink

die Ausgezeichnete Mitteilung))
https://mypblognews.wordpress.com/

http://toy-shop.top/
http://orshop.top/
http://randu.xyz/

http://sushenkovnfq5.tumblr.com/
http://medina-vera3v60.tumblr.com/
Reply
aspillic
2017年12月18日 at 下午1:15
Permalink

Wow! this cartoon type YouTube video I have seen when I was in primary level and at the moment I am in school and seeing that again here.
https://www.omaomk.com/index.php/topic,123818.new.html#new
http://www.vwloc.com/forum/viewtopic.php?f=17&t=1477

http://xn--80aeia7ahgddhp6b7a.xn--p1ai/forum/viewtopic.php?f=3&t=5202
http://milbrujas.com/anuncios/viewtopic.php?f=3&t=47089
http://techandplus.com/forum/showthread.php?tid=2748&pid=2988#pid2988
http://www.coronathailand.com/board/index.php?topic=468223.new#new

http://vision317.com/forum/index.php?/topic/160570-imagenes-de-mujeres-posando-desnudas-vision317com/
http://hatun.ru/forum/viewtopic.php?pid=49467#p49467
http://russian-anonymous-forum.biz/showthread.php?tid=5131
http://hiddenfog.ucoz.com/forum/6-361-1#13959
Reply
aspillic
2017年12月26日 at 上午5:00
Permalink

Cela ne sortait pas encore.
http://www.nbp.pw/results/alexis+texas+massage
http://www.pornbreeze.com/s/latex+movies

http://www.bangwhore.top/
http://bbw.buron.pw/

http://www.bangwhore.top/s/looking+up+at+pussy
http://www.milkscock.top/s/pull+down+pants
http://newbp.win/results/the+first+time+gay
Reply
Pingback: SPOJCOT2 Count on a tree II – AKteam

发表评论取消回复