QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 5096. 千百

Statistics

题目背景

千百次轰击,千百场碰撞,坚固的二〇一号大型引力子加速器完好如初。这是它的第千百个实验……

加速器中被高频扰动的引力场激发出 $n$ 个引力子。你们的实验目标是使得它们同时存在 $10^{-12}$ 秒。

这 $n$ 个引力子环状均匀地排列在加速器中。每个引力子拥有一定的引力焓,代表着它的能量。引力焓是一个离散的标量。不同于热力焓值,引力焓定义在整数域内,也就是说,它是可负的。当两引力子距离较近时,若它们的引力焓乘积非负,它们就会互相吸引、迅速湮灭;反之,当引力焓乘积为负,两粒子将会相斥、达到相对稳定的共存态。引力子独立存在时寿命很长,也就是说,这 $n$ 个引力子能稳定地共存 $10^{-12}$ 秒,当且仅当任意相邻的两个引力子不会湮灭。你们需要在引力子被激发后、它们湮灭前的极短时间内,通过若干次干涉改变这些引力子的引力焓,从而使得它们稳定地共存。

题目描述

现在,我们量化地描述这个实验。引力子排成环状,我们顺时针地给这些引力子编号,从 $0$ 到 $n-1$。也就是说,$i$ 号引力子会和 $(i-1)\bmod n$ 以及 $(i+1)\bmod n$ 号相邻。初始时,$i$ 号引力子的引力焓为 $a_i$ 个单位。你们需要使得对于所有的 $i\in [0,n)$,$a_i\times a_{(i+1)\bmod n} <0$。为了达到目的,你们可以进行若干次操作。每次操作时,你们可以选取一个引力子进行干涉。假如你们干涉的是 $i$ 号引力子,那么这会使得 $a_{(i-1)\bmod n}$ 与 $a_{(i+1)\bmod n}$ 同时减去 $a_i$,然后使 $a_i$ 变为 $-a_i$。你们不能同时干涉两个粒子。而你,需要计算出最少需要进行多少次这样的干涉。

不出意外地,接下来是你们遇到的意外。你们的实验在不可抗拒因素作用下被干扰了。具体来说,你们激发的引力子中会有相邻的两个 $p$ 号和 $(p+1)\bmod n$ 号,意外地同时增加 $v$ 的引力焓值。你们对干扰进行了预测,得到了 $m$ 种可能的情况。现在的你,需要对每种情况计算如果初始状态如上变化,最少需要进行多少次干涉。

当然,实验总有失败的可能性。如果你发现不可能通过干涉达到目标,也请你报告无解。

输入格式

输入文件有若干行,每行若干整数,同行相邻整数间用一个空格隔开。

第一行包含两个数 $n,m$。

第二行包含 $n$ 个数,第 $i$ 个数为 $a_{i-1}$ 。

接下来 $m$ 行,每行两个数 $p,v$,表示一次干扰预测。

输出格式

输出 $m$ 行,每行一个整数。第 $i$ 行的整数为你对第 $i$ 次预测的答复。如果该预测下可以达到目标,请你输出最少的干涉次数,否则请你输出 $-1$ 以表明无解。

输入输出样例

样例输入 #1

4 2
-1 5 5 3
0 2
2 -2

样例输出 #1

5
3

样例解释 #1

第二次猜测对应的一种方案:

    -1 +5 +3 +1
->  -1 +2 -3 -2
->  +1 +2 -1 +2
->  -1 +1 -1 +1

样例输入 #2

5 2
0 0 0 0 0
1 2
0 1

样例输出 #2

-1
-1

样例输入 #3

20 10
-25 33 -28 39 -2 33 -23 27 24 9 -38 -14 10 -24 -4 29 -9 25 17 37
12 -25
10 -24
16 1
2 47
0 -32
13 21
19 0
5 -23
3 24
1 41

样例输出 #3

20
23
21
22
21
20
21
21
22
22

数据范围

千百个实验,千百颗粒子,千百次猜测……一千个一百,就是你们的极限。

本题采用捆绑测试,分为以下若干个子任务,每个子任务对应不同的数据范围限制。若你通过一个子任务内的所有测试点,则你可以得到该子任务对应的得分。

  • Subtask 1 (10 pts): $1 \le n,m \le 50$,$|v|,|a_i| \le 50$。
  • Subtask 2 (20 pts): $1 \le n,m \le 400$。
  • Subtask 3 (30 pts): $1 \le n,m \le 10^5$,$v=0$。
  • Subtask 4 (40 pts): $1 \le n,m \le 10^5$。

此外,保证所有测试点满足:$n \ge 3$,$0 \le p < n$,$|v|,\sum_{i=0}^{n-1} |a_i| \le 10^8$,所有输入的数均为整数。