QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB

# 7465. Worst Case Top Tree

Statistics

给定序列 $a_0,a_1,a_2\dots,a_n,a_{n+1}$;

满足 $a_0=a_{n+1}=+\infty$,$a_1,a_2,\dots,a_n$ 在输入中给出;

对 $1\le x \le n$,称 $\max_{0\le i < x,a_i\ge a_x} i$ 和 $x$ 是相邻的,且 $\min_{x < i\le n+1,a_i>a_x} i$ 和 $x$ 是相邻的;

如果 $x$ 和 $y$ 相邻,则 $y$ 和 $x$ 也相邻;

如果 $0\le b_1,b_2,b_3,b_4,b_5,b_6\le n+1$,且 $b_i$ 和 $b_{i+1}$ 相邻,$b_1$ 和 $b_6$ 相邻,$b_i$ 互不相同,则称集合 $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ 是一个六元环(即判断两个六元环是否相同时,不考虑 $b_i$ 的顺序)。

共有 $m$ 次修改操作,每次修改操作给出 $x\;y$,将 $a_x$ 改为 $a_x+y$;

每次修改后要求输出六元环的个数;

输入格式

第一行一个整数 $n$;

第二行 $n$ 个整数表示 $a_1\;a_2\;\dots\;a_n$;

第三行一个整数 $m$;

接下来 $m$ 行,每行两个整数 $x\;y$ 表示一次修改操作。

输出格式

共 $m$ 行,每行一个整数,表示每次修改后的六元环个数。

样例数据

样例输入

6
1 2 5 4 3 6
4
1 8
3 6
5 10
2 7

样例输出

3
0
1
1

子任务

Idea:ccz181078,Solution:ccz181078,Code:ccz181078&zx2003,Data:nzhtl1477&zx2003

对于 $100\%$ 的数据,以上提到的所有数值为整数,且 $1\le n,m\le 5\cdot 10^5;\;1\le x\le n;\;1\le a_i,y\le 10^9$。