询问区间内出现次数等于1的数个数的单次小于根号算法

Shunpower @ 2022-08-11 19:09:01

by ningago @ 2022-08-11 19:12:05

莫队

by do_while_true @ 2022-08-11 19:12:11

离线之后按右端点扫描线，维护一下每个左端点对应的区间的答案

by syf2008 @ 2022-08-11 19:12:33

@Zealous_YH 您可能需要莫队

by 喵仔牛奶 @ 2022-08-11 19:12:46

主席树？

by jijidawang @ 2022-08-11 19:13:25

可以 O(n^3) 预处理 O(1) 查询（

by do_while_true @ 2022-08-11 19:13:35

扫描线扫 r 的时候让每个颜色在 [1,r] 中最后一次出现位置贡献 1，倒数第二次出现位置贡献 -1，求区间和 [l,r] 即为答案。

by Shunpower @ 2022-08-11 19:13:45

莫队总的来说是根号的吧，这也不太行。

希望得到 \log 一类的答案。

by Shunpower @ 2022-08-11 19:13:58

@jijidawang

草（（（（

by syf2008 @ 2022-08-11 19:14:48

@Zealous_YH 那就主席树

by Shunpower @ 2022-08-11 19:15:07

@syf2008

主席树怎么做啊 想了好久/jk