#P17587. 一人

一人

题目描述

给定 n,mn,m,以及序列 a1,a2,…,ana_1,a_2,\dots,a_n 和 1,2,…,n1,2,\dots,n 的排列 y1,y2,…,yny_1,y_2,\dots,y_n,你需要回答 mm 个询问。

对每个询问,给定 l,rl,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]$;

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

输入格式

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

第二行 nn 个整数 a1,…,ana_1,\dots,a_n;

第三行 nn 个整数 y1,…,yny_1,\dots,y_n;

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

0
1
1
0

说明/提示

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

对于 20%20\% 的数据,满足 n,m≤100n,m\le 100。

对于 40%40\% 的数据,n,m≤5000n,m\le 5000

对于 60%60\% 的数据,n,m≤2×105n,m\le 2\times 10^5