7099：Just Another Data Structure Problem

题目描述

给定 $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(1\leq n\leq 10^5, 1\leq m\leq 10^6)$。

第二行包含 $n$ 个整数 $a_1, \dots, a_n (1 \leq a_i \leq n)$。

第三行包含 $n$ 个整数 $y_1, \dots, y_n(1 \leq y_i \leq n)$，保证 $y_i$ 互不相同。

接下来 $m$ 行，每行两个数 $l, r (1 \leq l \leq r \leq n)$ 表示一个询问。

输出解释

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

输入样例

输出样例

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021 年百度之星·程序设计大赛 - 复赛

源链接： HDU-7099

最后修改于 2021-10-23T19:11:25+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
10000/5000MS(Java/Others)	262144/262144K(Java/Others)