计蒜客

  1. 题库
  2. 百度科学家(困难)
  3. 问答
  • 18.01%
  • 1000ms
  • 262144K

百度有一位非常有名的大科学家,这位大科学家有很多藏书。

大科学家有一个图书馆,所以放书的容量也随之增加了,图书馆可以看成一个长度为 $N$ 的序列,一开始里面放着 $N$ 本书,每本书都记载了一个特定元素的信息,书中的元素各不相同。

大科学家会先进行若干次研究,最后进行一次科学实验,这次实验需要选取一些元素放在一起来进行。每次研究,大科学家会从图书馆中的某些位置抽出一些书来看,然后得出“如果 $x$ 位置上的书对应的元素被拿来做实验了,那么区间 $[l,r]$ 位置上的书对应的元素也必须拿来做实验,否则会爆炸”这样的结论。

大科学家有不止 $N$ 本书(也就是说世界上有不止 $N$ 种元素),但是他自己没时间给图书馆换书,所以他雇了一个实习生,这个实习生会时不时地拿出一本从来没被放入图书馆的书,然后替换掉图书馆中某个位置原来的书。所以对于大科学家得到的两次看似一样的研究结果,可能由于图书馆中的书被换了,它们的实质内容可能不一样

每本书还记载着对应元素的非负污染值,大科学家希望在完成一次科学实验的前提下(不能不选任何元素),这次实验的总污染值最小。作为一个旁观者,你能看到科学家做的所有研究结果以及实习生换书的顺序,然后你需要告诉大科学家,这个最小总污染值是多少。

听说马上要科技胜利了,大科学家精力充沛,再也不用担心他的实验结论受到限制了。

输入格式

第一行一个正整数 $N$,代表图书馆的容量。

接下来一行 $N$ 个数,第 $i$ 个非负整数 $a_i$ 代表最开始图书馆中第 $i$ 本书所描述的元素的污染值。

接下来一行一个整数 $M$,代表事件的总数。

接下来 $M$ 行,每行代表一个事件:

若为 $0$ $x$ $y$,代表实习生拿了一本新书替换了 $x$ 位置的书,新书对应元素的污染值为 $y$。

若为 $1$ $x$ $l$ $r$,代表大科学家得到了新的结果,如果 $x$ 位置的书对应的元素加入了实验,那么 $[l,r]$ 区间内的书对应的元素都必须拿来做实验。

保证大科学家的书籍总数 $(N+$ 新书数量 $) \le 10^5$。

每个元素的污染值 $0\le (a_i,y) \le 10^9$。

保证 $1 \le x \le N$,$1 \le l \le r \le N$,$M \le 10^5$。

输出格式

输出一个整数,代表最小总污染值。

样例解释

一开始书架上有 $5$ 本书,我们记这些元素的编号顺次为 $1,2,3,4,5$,他们的污染值分别为 $1,10,100,1000,10000$。

一共有 $4$ 个事件:

  1. 大科学家发现,选了元素 $1$ 就必须选元素 $3,4$。

  2. 大科学家发现,选了元素 $3$ 就必须选元素 $5$。

  3. 实习生拿了一本新书,我们记这个新元素的编号为 $6$,他的污染值为 $0$,替换掉现在书架上的第 $3$ 本书,现在书架上的 $5$ 本书对应元素为 $1,2,6,4,5$。

  4. 大科学家发现,选了元素 $6$(因为它在位置 $3$ 上)就必须选元素 $1,2$。

于是在所有可能的方案中,单选一个元素 $2$ 来做实验是总污染值最小的,因为如果选择元素 $1$ 或元素 $6$,都存在一些绑定关系使得总污染值不可能比 $10$ 更小。

样例输入

5
1 10 100 1000 10000
4
1 1 3 4
1 3 5 5
0 3 0
1 3 1 2

样例输出

10

想挑战这道题吗

  • main.c