求助给动态集合中的点连边的问题

学术版

喵仔牛奶 @ 2023-08-05 19:05:52

如题，有 n 个数和一个集合 S，每次添加或删除若干数（一个数不会被添加或删除多次），操作完后给出一个点 x（x 尚未被添加进集合中），将 x 向集合内所有数连一条有向边。

所有操作进行完后，需要进行一次遍历。

请问最好可以做到什么复杂度，需要连多少条边 qwq

by ღꦿ࿐ @ 2023-08-05 19:15:33

这个是不是可以线段树分治啊，求出每个点在集合中的时间段然后向这段时间内的 S 通过线段树连边。

by expnoi @ 2023-08-05 19:15:41

@喵仔牛奶请问添加或删除一个数是把哪里的数放到哪里。这个遍历具体的定义是什么？起点是什么？有原题吗？

by ღꦿ࿐ @ 2023-08-05 19:16:46

@喵仔牛奶

by ღꦿ࿐ @ 2023-08-05 19:17:34

向这段时间内的 S \to 向这段时间内的 x

by 喵仔牛奶 @ 2023-08-05 19:24:24

@small_rubbish 是将原来的 n 个数放入集合或删除。遍历的起点给定。没有原题。

by 喵仔牛奶 @ 2023-08-05 19:25:35

@ღꦿ࿐ 好像对的。