bzoj#P3956. Count

Count

题目描述

给定一个长度为 nn 的序列 a1na_{1\cdots n},定义 (i,j)(i,j)(规定 i<ji<j)为好点对,当且仅当满足下列条件之一:

  • i=j1i=j-1
  • k(i,j),akmin{ai,aj}\forall k\in(i,j),a_k\leq \min\{a_i,a_j\}

现在有 mm 组询问区间 [l,r][l,r] 内好点对的个数。

给定一个 typetype,当 type=0type=0 的时候不强制在线,否则强制在线,具体操作请看输入格式。

输入格式

1mod91 \bmod 9 第一行三个整数 n,m,typen,m,type,意义同题目描述。

第二行 nn 个整数 a1na_{1\cdots n}

接下来 mm 行,每行两个非负整数 l,rl,r。当 type=0type=0,询问区间就是 [l,r][l,r],否则令 u=(l+last1)modn+1,v=(r+last1)modn+1u=(l+last-1)\mod n+1,v=(r+last-1)\bmod n+1,那么当前询问区间就是 [min{u,v},max{u,v}][\min\{u,v\},\max\{u,v\}],其中 lastlast 是上一次询问的答案,初始时 last=0last=0

输出格式

mm 行,第 ii 行一个非负整数表示第 ii 次询问的答案。

3 2 0
2 1 2
1 1
1 3
0
3

数据规模与约定

对于 100%100\% 的数据,1n,m3×1051\leq n,m\leq 3\times 10^5ai109|a_i|\leq 10^9