P6604 [HNOI2016] 序列 加强版

本题是 [P3246](https://www.luogu.com.cn/problem/P3246) 的数据加强版，扩大了询问次数的范围，增加了强制在线，并加入了一组构造数据。 本题的输入输出格式与原题略有不同。

给定长度为 $ n $ 的序列：$ a_1, a_2, \cdots , a_n $，记为 $ a[1 \colon n] $。类似地，$ a[l \colon r] $（$ 1 \leq l \leq r \leq N$）是指序列：$ a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r $。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $ a[s \colon t] $是 $ a[l \colon r] $ 的子序列。 现在有 $ q $ 个询问，每个询问给定两个数 $ l $ 和 $ r $，$ 1 \leq l \leq r \leq n $，求 $ a[l \colon r] $ 的不同子序列的最小值之和。例如，给定序列 $ 5, 2, 4, 1, 3 $，询问给定的两个数为 $ 1 $ 和 $ 3 $，那么 $ a[1 \colon 3] $ 有 $ 6 $ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] $，这 $6 $ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

无

无

- 对于 $30\%$ 的数据，$1\le q\le10^5$，$type=0$。 - 对于另外 $70\%$ 的数据，$1\le q\le10^7$，$type=1$。 对于 $100\%$ 的数据，$1\le n\le10^5$，$-10^9\le a_i\le10^9$。