/ JF_OIer / 题库 /

小lyh的魔法炮

小lyh的魔法炮

题目背景

传说上古时期,发生了一场极其惨烈的战争,有一方决定建立了许多魔法炮,这些魔法炮威力比人类的氢弹还要大

题目描述

这些魔法炮被放置在一条长为\(n\)的河岸上,从\(1\)到\(n\)每个位置上都有一个炮塔,第\(i\)个炮塔的位置为\(i\),且炮塔不会移动,初始时每个炮塔上都只有一门炮,每门炮都有一个威力值,炮之间可能会发生冲突。设两门炮之间的"冲突程度"为这两门炮的位置之差与威力值之差的和。炮塔上可能会新增一些炮,且炮不会消失,及炮塔上可能有很多门炮。

现在,另一方的首领想随时知道:对于某个炮塔上的主炮(主炮是指该炮塔上最迟添加的一门炮,没添加则是初始的那门炮),有多少门炮(是炮不是炮塔!!)与其的冲突程度\( \le k\)(包括该门炮和同一炮塔上的炮)

有时炮塔上会新增一门炮,当然这也会告诉你

输入输出格式

输入格式:

第一行输入两个数\(n\),\(q\),及炮塔数和操作数

第二行输入\(n\)个数,为初始时炮塔上的炮的威力值

第3~2+q行,两种操作:
1. Q x k:询问有多少门炮与第\(x\)个炮塔上的主炮的冲突程度\( \le k\)
2. A x k:在第\(x\)个炮塔上新增一门威力值为\(k\)的炮

输出格式:

对于每次询问,输出一个非负整数表示答案

Sample 1

Input

3 5
2 4 3
Q 2 2
A 1 3
Q 2 2
A 1 2
Q 1 1

Output

2
3
3

时空限制

1~2s, 256000KiB for each test case.

说明

  • \(n \le 60000\)
  • 修改操作数\( \le 40000\)
  • 询问数\( \le 50000\)
  • 过程中炮的威力值\(\le 100000\)