题目描述
给定一个长度为 n 的序列 a1⋯n,定义 (i,j)(规定 i<j)为好点对,当且仅当满足下列条件之一:
- i=j−1;
- ∀k∈(i,j),ak≤min{ai,aj}。
现在有 m 组询问区间 [l,r] 内好点对的个数。
给定一个 type,当 type=0 的时候不强制在线,否则强制在线,具体操作请看输入格式。
输入格式
1mod9
第一行三个整数 n,m,type,意义同题目描述。
第二行 n 个整数 a1⋯n。
接下来 m 行,每行两个非负整数 l,r。当 type=0,询问区间就是 [l,r],否则令 u=(l+last−1)modn+1,v=(r+last−1)modn+1,那么当前询问区间就是 [min{u,v},max{u,v}],其中 last 是上一次询问的答案,初始时 last=0。
输出格式
共 m 行,第 i 行一个非负整数表示第 i 次询问的答案。
3 2 0
2 1 2
1 1
1 3
0
3
数据规模与约定
对于 100% 的数据,1≤n,m≤3×105,∣ai∣≤109。