#P7604. [2018年杭电多校]foam-transformation

[2018年杭电多校]foam-transformation

foam-transformation

题目描述

For an array of length mm, an operation T i k (1≤i<m1\le i<m, with integer kk) adds

$$a_j\mathrel{+}= (j-i+1)^2(-1)^k\qquad(i\le j\le m),$$

and leaves earlier entries unchanged. The parity of kk selects the plus or minus sign. Any finite number of these operations may be used.

A array aa with length nn is "acid" if and only if :

  1. If we add 55 zero elements at the end of aa (length is n+5n + 5 now).
  2. 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 al,al+1...ara_{l},a_{l+1}...a_{r} is "acid",1≤l≤r≤length(a)1 \le l \le r \le length(a))
    Now,you are given an integer nn and an array "a" consisting nn integers.You should maintain the "acidity" of the array dynamicly. Given an integer m, following m operations like that: U i x adds xx to both aia_i and ai+1a_{i+1} (1≤i<n1\le i<n). 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 TT (no morn than 10), the following is TT test case, for each test case : The first line,two integers n and m, satisfying 2≤n≤100000,1<m≤1000002 \le n \le 100000,1 < m \le 100000. 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,1≤i<n,∣x∣≤1000001 \le i < n,|x| \le 100000,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