QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB

# 7434. 冷たい部屋、一人

统计

给定 $n,m$,以及序列 $a_1,a_2,\dots,a_n$ 和 $1,2,\dots,n$ 的排列 $y_1,y_2,\dots,y_n$,你需要回答 $m$ 个询问。

对每个询问,给定 $l,r$,查询:

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i=a_j]\cdot\prod_{k=i}^j [l\le y_k\le r]$$

其中 $[\mathrm{cond}]$ 在条件 $\mathrm{cond}$ 为真时值为 $1$,否则值为 $0$。

输入格式

第一行两个数 $n,m$;

第二行 $n$ 个整数 $a_1,\dots,a_n$;

第三行 $n$ 个整数 $y_1,\dots,y_n$;

接下来 $m$ 行,每行两个数 $l,r$ 表示一个询问。

输出格式

$m$ 行,每行一个整数,表示相应的答案。

样例数据

样例输入

3 4
1 1 3
2 3 1
1 2
1 3
2 3
1 1

样例输出

0
1
1
0

子任务

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

对于 $100\%$ 的数据,满足 $1\le n,m\le 5\times 10^5$;$1\le a_i\le n$;$1\le y_i\le n$,$y_i$ 互不相同;对每个询问,$1\le l\le r\le n$。

对于 $25\%$ 的数据,满足 $n,m\le 100$。

对于 $50\%$ 的数据,$n,m\le 5000$

对于 $75\%$ 的数据,$n,m\le 2\times 10^5$