#P7604. [2018年杭电多校]foam-transformation
[2018年杭电多校]foam-transformation
foam-transformation
题目描述
For an array of length , an operation T i k (, with integer ) adds
and leaves earlier entries unchanged. The parity of selects the plus or minus sign. Any finite number of these operations may be used.
A array with length is "acid" if and only if :
- If we add zero elements at the end of (length is now).
- After 1, we can use finite operation "T" on a to make a become all zero array.
The "acidity" of a array "a" is the number of nonempty subintervals which is "acid".
(more formally, the number of pairs (l,r) satisfying is "acid",)
Now,you are given an integer and an array "a" consisting integers.You should maintain the "acidity" of the array dynamicly. Given an integer m, following m operations like that:U i xadds to both and (). These updates change the original array; they are different from the operations used in the definition of acid subarrays. You should output an answer before all operations, Then print one more answer after each operation denoting the dynamic "acidity". Yes, as the writer is too lazy, we didn't encrypt the input data in any way, help yourself if you can solve this problem by some off line way :)
输入格式
The first line contain a integer (no morn than 10), the following is test case, for each test case : The first line,two integers n and m, satisfying . The second line consists n integers whose absolute values are not greater than 100000. Next m lines,each would be shown like U i x,,which denotes a modifying operation.
输出格式
Print m+1 answers one perline denoting the dynamic "acidity" of the given array.
样例输入 1
1
20 10
-63541 0 -59055 -41170 0 0 0 -21343 25072 0 -76818 -59156 0 4435 59829 0 0 -56094 0 0
U 5 -62470
U 13 -52045
U 18 95988
U 13 -76265
U 7 35037
U 6 -41898
U 8 -71979
U 18 48427
U 16 -4208
U 15 34206
样例输出 1
15
12
11
9
9
7
6
6
6
4
3
Source
2018 Multi-University Training Contest 6