#1543. 「CodePlus #7」六元环

    ID: 1543 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构Link-Cut Tree笛卡尔树 / Kruskal 重构树CodePlus2020

「CodePlus #7」六元环

题目描述

qwqwq。


给定序列 a0,a1,,an,an+1a_0, a_1, \dots, a_n, a_{n+1};满足 a0=an+1=+a_0 = a_{n+1} = +\inftya1,a2,,ana_1, a_2, \dots, a_n 在输入中给出;

1xn1\le x\le n,称 max0i<x,aiaxi\max_{0\le i<x, a_i\ge a_x} ixx 是相邻的,且 minx<in+1,ai>axi\min_{x< i\le n+1, a_i>a_x} ixx相邻的;如果 xxyy 相邻,则 yyxx 也相邻;

如果 0b1,b2,b3,b4,b5,b6n+10 \le b_1, b_2, b_3, b_4, b_5, b_6\le n+1,且 bib_ibi+1b_{i+1} 相邻,b1b_1b6b_6 相邻,bib_i 互不相同,则称集合 {b1,b2,b3,b4,b5,b6}\{b_1,b_2,b_3,b_4,b_5,b_6\} 是一个六元环(即判断两个六元环是否相同时,不考虑 bib_i 的顺序)。

共有 mm 次修改操作,每次修改操作给出 x yx\ y,将 axa_x 改为 ax+ya_x + y;每次修改后要求输出六元环的个数;

以上提到的所有数值为整数,且 $1\le n, m\le 5\times 10^5, 1\le x\le n,1\le a_i, y\le 10^9$。

输入格式

第一行一个整数 nn

第二行 nn 个整数表示 a1,a2,,ana_1, a_2, \dots, a_n

第三行一个整数 mm;接下来 mm 行,每行两个整数 x yx\ y 表示一次修改操作。

输出格式

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

样例

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

数据范围与提示

子任务 分数 限制
11 1010 max(n,m)100\max (n,m)\le 100
22 1010 max(n,m)2000\max (n,m)\le 2000
33 2020 max(n,m)50000\max (n,m)\le 50000
44 2020 for each operation, x100x\le 100
55 2020 for each operation, y10y\le 10
66 2020