### 差分

#### 一维差分

1. 首先我们让差分数组diff[l]加上增量c，即diff[i]+c，那么根据定义很容易我们就可以推得，此时a[i]、a[i+1]、….、a[r]、a[r+1]、…、a[n]都增加了一个增量c，即此时自l以右的元素全部增加了c
2. 但是我们只是想要 [l,r]内的元素增加一个增量c，因此我们还需要进一步操作将a[r+1]即以后的元素再减去一个增量，因此还需要进行diff[r+1]-c的操作

q次操作以后，我们就该输出每一个变化后的num元素了，前面我们讲到了num数组实际上就可以看成是差分数组的前缀和数组，因此num[i]的计算公式就是：

### 算法练习

…………

#### 2）子矩阵求和

##### 数据范围

n×m≤100,000，a[i][j] <=1000，q<=100,000，1<=a<=c<=n，1<=b<=d<=m。

#### 3）Margarite and the best present

##### 题目描述

Little girl Margarita is a big fan of competitive programming. She especially loves problems about arrays and queries on them.

Recently, she was presented with an array aa of the size of 10^9109 elements that is filled as follows:

• a1 = -1
• a2 = 2
• a3 = -3
• a4 = 4
• a5 = -5
• And so on …

That is, the value of the i-th element of the array a is calculated using the formula.

She immediately came up with q queries on this array. Each query is described with two numbers: land r. The answer to a query is the sum of all the elements of the array at positions from l to r inclusive.

Margarita really wants to know the answer to each of the requests. She doesn’t want to count all this manually, but unfortunately, she couldn’t write the program that solves the problem either. She has turned to you — the best programmer.

##### 输入描述

The first line contains a single integer q (1<=q<=1e3) — the number of the queries.

Each of the next q lines contains two integers l and r (1<=l<=r <=1e9) — the descriptions of the queries.

##### 输出描述

Print q lines, each containing one number — the answer to the query.

##### 样例说明

In the first query, you need to find the sum of the elements of the array from position 1 to position 3. The sum is equal to a1 + a2 + a3 = -1 + 2 -3 = −2.

In the second query, you need to find the sum of the elements of the array from position 2 to position 5. The sum is equal to a2 + a3 + a4 + a5 = 2 -3 + 4 - 5 =−2.

In the third query, you need to find the sum of the elements of the array from position 5 to position 5. The sum is equal to a5 = -5.

In the fourth query, you need to find the sum of the elements of the array from position 4 to position 4. The sum is equal to a4 = 4.

In the fifth query, you need to find the sum of the elements of the array from position 2 to position 3. The sum is equal to a2+a3 = 2 - 3 =−1.

##### 解题思路

pre=[-1,1,-2,2,-3,3,-4,4,-5,5…]，很明显对于第i个前缀和元素pre[i]，当i为奇数时必定为负数，同时pre[i]的数值的绝对值有如下规律：

#### 4）Star Sky

##### 题目描述

The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (xi, yi), a maximum brightness c, equal for all stars, and an initial brightness si (0 ≤ si ≤ c).

Over time the stars twinkle. At moment 0 the i-th star has brightness si. Let at moment t some star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if x + 1 ≤ c, and 0, otherwise.

You want to look at the sky q times. In the i-th time you will look at the moment ti and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x1i, y1i) and the upper right — (x2i, y2i). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.

##### 输入描述

The first line contains three integers n, q, c (1 ≤ n, q ≤ 1e5, 1 ≤ c≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars.

The next n lines contain the stars description. The i-th from these lines contains three integers xi, yi, si (1 ≤ xi,yi ≤ 100, 0 ≤ si ≤ c ≤ 10) — the coordinates of i-th star and its initial brightness.

The next q lines contain the views description. The i-th from these lines contains five integers ti, x1i, y1i, x2i, y2i (0 ≤ ti ≤ 1e9, 1 ≤ x1i < x2i ≤ 100, 1 ≤ y1i < y2i ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.

##### 输出描述

For each view print the total brightness of the viewed stars.

##### 样例说明

Let’s consider the first example.

At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.

At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.

At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.

#### 5）Matrix Subtraction

##### 题目描述

Given a matrix M of size n×m and two integers a,b，determine weither it is possible to make all entrys of M zero by repeatedly choosing a×b submatrices and reduce the values in the chosen matrices by 1. If possible, print ^_^ in one line, or print QAQ in one line.

##### 输入描述

The first line contains one integer T (1≤T≤100), denoting the number of test cases.

For each test case:

The first line contains four integers n,m,a,b (1≤n,m≤1000,1≤a≤n,1≤b≤m), denoting the size of given matrix and the size of chosen submatrices respectively.

The next n lines each contains m integers Mi,j (0≤Mi,j≤109), denoting the entrys of matrix M.

It’s guaranteed that ∑nm≤1e6.

##### 输出描述

Print T lines each containing a string ^_^ or QAQ, denoting the answer to each test case.

##### 样例说明

For the second case, one possible scheme is to choose (1,1)−(1,2),(1,2)−(1,3),(2,1)−(2,2),(2,2)−(2,3) respectively.