题目描述

定义一个数组 $b = \{b_1, b_2, \dots, b_n\}$ 的权值为：

$$\sum_{i = 1}^{n - 1}\left(\left(\left(b_{i + 1} - b_{i}\right) \bmod 5 + 5\right)\bmod 5\right)$$

现在给定一个长为 $n$ 的数组 $a = \{a_1, a_2, \dots, a_n\}$，76会对这个数组进行 $q$ 次如下操作：

  • 给出两个整数 $l, r (1 \leq l \leq r \leq n)$，将区间 $[l, r]$ 内的所有元素加 1。
  • 请你在每次操作后输出当前数组的权值。注意，每次操作不独立。

输入描述

第一行输入两个整数 n, q (1 ≤ n, q ≤ 2×10^5)
第二行输入 n 个整数 a1, a2, …, an (0 ≤ ai ≤ 10^9)
之后的 q 行，每行输入两个整数 l, r (1 ≤ l ≤ r ≤ n)，代表一次操作。

输出描述

对于每次操作，新起一行输出一个整数，代表操作后数组的权值。

示例

输入

3 2
1 2 3
1 2
2 3

输出

1
2

题解代码

#include <bits/stdc++.h>
using namespace std;

const int N = 501;

#define int long long

signed main() {
    int n, q;
    int total = 0;
    int a[200001];
    int d[20001];
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        if (l > 1) {
            total -= (d[l-1] % 5 + 5) % 5;
            d[l-1]++;
            total += (d[l-1] % 5 + 5) % 5;
        }
        if (r < n) {
            total -= (d[r] % 5 + 5) % 5;  // 每一次计算都不要忘了进行取模运算
            d[r]--;
            total += (d[r] % 5 + 5) % 5;
        }
        cout << total << endl;
    }
    
    return 0;
}