致疯狂的人。他们特立独行。他们桀骜不驯。他们惹是生非。他们格格不入。他们用与众不同的眼光看待事物。他们不喜欢墨守成规。他们也不愿安于现状。你可以认同他们，反对他们，颂扬或是诋毁他们。但唯独不能漠视他们。因为他们改变了寻常事物。他们推动人类向前迈进。或许他们是别人眼里的疯子，但他们却是我们眼中的天才。因为只有那些疯狂到以为自己能够改变世界的人…… 才能真正改变世界。

最近又好颓废呀，暑假想写的两道树状数组的题解拖到了今天。

Movie Collection(NWERC 2011)

传送门： Gym - 100729C

Problem

Description

Mr. K. I. has a very big movie collection. He has organized his collection in a big stack.
Whenever he wants to watch one of the movies, he locates the movie in this stack and removes
it carefully, ensuring that the stack doesn’t fall over. After he finishes watching the movie, he
places it at the top of the stack.
Since the stack of movies is so big, he needs to keep track of the position of each movie.
It is sufficient to know for each movie how many movies are placed above it, since, with this
information, its position in the stack can be calculated. Each movie is identified by a number
printed on the movie box.
Your task is to implement a program which will keep track of the position of each movie.
In particular, each time Mr. K. I. removes a movie box from the stack, your program should
print the number of movies that were placed above it before it was removed.

尺取法、单调队列、滑动窗口一直傻傻分不清。以前觉得尺取法就是滑动窗口，现在又觉得单调队列和滑动窗口是一回事。

算法的美妙之处就在于当你明了一个算法时，会发自内心惊叹它的美。我于树状数组如此，学习单调队列后亦如此。

关于单调队列的用法主要看了下单调队列及其应用中的内容， 以下引用一些内容。

单调队列及其应用

单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。

单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为o（1），由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是o（1）。

如何维护单调队列呢，以单调递增序列为例：

1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。

2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止

要特别注意头指针和尾指针的应用。

传送门:Northeastern European Regional Contest 2011 E. Eve

Problem

Input file: eve.in
Output file: eve.out

Mitochondrial DNA is the Deoxyribonucleic acid molecule that is contained in mitochondria within cellsof an organism. Mitochondrial DNA is normally passed to a child exclusively from its mother. Because of this fact, it is possible to speak of “Mitochondrial Eve” which refers to the most recent common matrilineal ancestor of the entire population. Matrilineal ancestry is traced through female line: mother, grandmother, etc. Mitochondrial Eve of the Earth’s human population is estimated to have lived around 200 000 years ago, most likely in the East Africa.

传送门:LightOJ 1269..Consecutive Sum

Problem

Description

Little Jimmy is learning how to add integers. As in decimal the digits are 0 to 9, it makes a bit hard for him to understand the summation of all pair of digits. Since addition of numbers requires the knowledge of adding digits. So, his mother gave him a software that can convert a decimal integer to its binary and a binary to its corresponding decimal. So, Jimmy’s idea is to convert the numbers into binaries, and then he adds them and turns the result back to decimal using the software. It’s easy to add in binary, since you only need to know how to add (0, 0), (0, 1), (1, 0), (1, 1). Jimmy doesn’t have the idea of carry operation, so he thinks that

1 + 1 = 0

1 + 0 = 1

0 + 1 = 1

0 + 0 = 0

Using these operations, he adds the numbers in binary. So, according to his calculations,

3 (011) + 7 (111) = 4 (100)

Now you are given an array of n integers, indexed from 0 to n-1, you have to find two indices i j in the array (0 ≤ i ≤ j < n), such that the summation (according to Jimmy) of all integers between indices i and j in the array, is maximum. And you also have to find two indices, p q in the array (0 ≤ p ≤ q < n), such that the summation (according to Jimmy) of all integers between indices p and q in the array, is minimum. You only have to report the maximum and minimum integers.

Input

Input starts with an integer **T (**≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 50000). The next line contains n space separated non-negative integers, denoting the integers of the given array. Each integer fits into a 32 bit signed integer.

Output

For each case, print the case number, the maximum and minimum summation that can be made using Jimmy’s addition.

Sample Input

2

5

6 8 2 4 2

5

3 8 2 6 5

Sample Output

Case 1: 14 2

Case 2: 15 1

Note

Dataset is huge, use faster I/O methods.

Solution

传送门: 2018 牛客网暑期 ACM 多校训练营 (第五场) F.take

Problem

Description

Kanade has n boxes , the i-th box has p[i] probability to have an diamond of d[i] size.

At the beginning , Kanade has a diamond of 0 size. She will open the boxes from 1-st to n-th. When she open a box,if there is a diamond in it and it’s bigger than the diamond of her , she will replace it with her diamond.

Now you need to calculate the expect number of replacements.

You only need to output the answer module 998244353.

Accepts: 791 Submissions: 2435
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem

Description

度度熊专门研究过 “动态传递闭包问题”，他有一万种让大家爆蛋的方法；但此刻，他只想出一道简简单单的题 —— 至繁，归于至简。

度度熊有一张 n 个点 m 条边的无向图，第 $i$ 个点的点权为 $v_i$。

如果图上存在一条路径使得点 i 可以走到点 j，则称 i,j 是带劲的，记 $f (i,j)=1$；否则 $f (i,j)=0$。显然有 $f (i,j) = f (j,i)$。

度度熊想知道求出：$\sum ^{n-1}{i=1} \sum^{n}{j=i+1} f(i, j) \times \max(v_i, v_j) \times (v_i & v_j)$

我失去了一只臂膀， 就睁开了一只眼睛。
—— 顾城

Problem

Given an unsorted integer array, find the smallest missing positive integer.

传送门：Fire Game

人一我百！人十我万！永不放弃～～～怀着自信的心，去追逐梦想 ——kuangbin

Problem

Description

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)