4.比赛

题目描述

输入

输出

样例输入输出

输入#1 复制

输出#1 复制

提示

**【样例 1 解释】**

当 $p = 1, q = 2$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $2 \times 2 = 4$。

当 $p = 1, q = 1$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $1$ 号选手，比赛精彩程度为 $2 \times 1 = 2$。

当 $p = 2, q = 2$ 的时候，小 N 会派出 $2$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $1 \times 2 = 2$。

**【数据范围】**

对于所有数据，保证：$1 \leq n, Q \leq 2.5 \times 10 ^ 5$，$1 \leq l _ i \leq r _ i \leq n$，$1 \leq a _ i, b _ i \leq n$ 且 $\{a _ i\}$ 和 $\{b _ i\}$ 分别构成了从 $1$ 到 $n$ 的排列。

| 测试点 | $n$ | $Q$ | 特殊性质 A | 特殊性质 B |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1, 2$ | $\leq 30$ | $\leq 30$ | 是 | 是 |
| $3, 4, 5$ | $\leq 3,000$ | $\leq 3,000$ | 是 | 是 |
| $6, 7$ | $\leq 10 ^ 5$ | $\leq 5$ | 是 | 是 |
| $8, 9$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 5$ | 是 | 是 |
| $10, 11$ | $\leq 10 ^ 5$ | $\leq 5$ | 否 | 否 |
| $12, 13$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 5$ | 否 | 否 |
| $14, 15$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | 是 | 是 |
| $16, 17$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | 是 | 是 |
| $18, 19$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | 是 | 否 |
| $20, 21$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | 是 | 否 |
| $22, 23$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | 否 | 否 |
| $24, 25$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | 否 | 否 |

特殊性质 A：保证 $a$ 是均匀随机生成的 $1 \sim n$ 的排列。

特殊性质 B：保证 $b$ 是均匀随机生成的 $1 \sim n$ 的排列。

6225: 4.比赛

题目描述

输入

输出

样例输入输出

提示

题目信息

模拟

数学与数论

动态规划

贪心

字符串

排序

枚举

数组与串

深搜

高精度

循环结构

递推

递归

二分三分

宽搜

背包

质数

线段树

分治

N进制

图论

队列

最短路

堆

树

并查集

栈

状态压缩

分支结构

几何

博弈论

生成树

顺序结构

离散化

hash表

位运算

单调队列

树状数组

KMP

字典树

二分图

数学期望

AC自动机

树链剖分

差分约束

数位动态规划

函数与过程

网络流

单调栈

前缀和