当前位置:首页 > 数据结构 > 线段树 > 正文
洛谷P8868比赛(NOIP2022)
127+

题目大意:两个长度为n的数列a和b,有m个询问,每次询问[l, r]中任意区间a、b最大值乘积之和。

题目描述

小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP!小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍,选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的,小 N 率领的队伍中,编号为 $i$($1 \leq i \leq n$)的选手的程序设计水平为 $a _ i$;小 O 率领的队伍中,编号为 $i$($1 \leq i \leq n$)的选手的程序设计水平为 $b _ i$。特别地,$\{a _ i\}$ 和 $\{b _ i\}$ 还分别构成了从 $1$ 到 $n$ 的排列。

每场比赛前,考虑到路途距离,选手连续参加比赛等因素,小 P 会选择两个参数 $l, r$($1 \leq l \leq r \leq n$),表示这一场比赛会邀请两队中编号属于 $[l, r]$ 的所有选手来到现场准备比赛。在比赛现场,小 N 和小 O 会以掷骰子的方式挑选出参数 $p, q$($l \leq p \leq q \leq r$),只有编号属于 $[p, q]$ 的选手才能参赛。为了给观众以最精彩的比赛,两队都会派出编号在 $[p, q]$ 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 $m _ a$,小 O 派出的选手水平为 $m _ b$,则比赛的精彩程度为 $m _ a \times m _ b$。

NOIP 总共有 $Q$ 场比赛,每场比赛的参数 $l, r$ 都已经确定,但是 $p, q$ 还没有抽取。小 P 想知道,对于每一场比赛,在其所有可能的 $p, q$($l \leq p \leq q \leq r$)参数下的比赛的精彩程度之和。由于答案可能非常之大,你只需要对每一场答案输出结果对 $2 ^ {64}$ 取模的结果即可。

输入输出格式

输入格式

第一行包含两个正整数 $T, n$,分别表示测试点编号和参赛人数。如果数据为样例则保证 $T = 0$。

第二行包含 $n$ 个正整数,第 $i$ 个正整数为 $a _ i$,表示小 N 队伍中编号为 $i$ 的选手的程序设计水平。

第三行包含 $n$ 个正整数,第 $i$ 个正整数为 $b _ i$,表示小 O 队伍中编号为 $i$ 的选手的程序设计水平。

第四行包含一个正整数 $Q$,表示比赛场数。

接下来的 $Q$ 行,第 $i$ 行包含两个正整数 $l _ i, r _ i$,表示第 $i$ 场比赛的参数 $l, r$。

输出格式

输出 $Q$ 行,第 $i$ 行包含一个非负整数,表示第 $i$ 场比赛中所有可能的比赛的精彩程度之和对 $2 ^ {64}$ 取模的结果。

输入输出样例

输入样例 #1

0 2
2 1
1 2
1
1 2

输出样例 #1

8

输入样例 #2

见附件下的 match/match2.in。

输出样例 #2

见附件下的 match/match2.ans。

输入样例 #3

见附件下的 match/match3.in。

输出样例 #3

见附件下的 match/match3.ans。

说明

**【样例 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$。

**【样例 2】**

该样例满足测试点 $1 \sim 2$ 的限制。

**【样例 3】**

该样例满足测试点 $3 \sim 5$ 的限制。

**【数据范围】**

对于所有数据,保证:$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$ 的排列。

解题思路

暴力做法:8分,不用说!

离线做法:20分!运用扫描线的知识,对所有询问按照r排序。对于询问[l, r],我们将任意区间按照左端点分类,左端点为i的和为c[i],答案即$\sum{^r_{i=l}}c[i]$。首先考虑如何维护c[i],增加一个右端点,就是增加max(a[l..r]) * max(b[l..r]);接着考虑如何维护最大值,左端点固定,右端点不递减,最大值不递减,新增一个a[r],一直往前,比他小的全部改成他即可。最后,将每个左端点为i的c[i]加上a[i]*b[i]即可。

满分做法:代码第25、26行为区间赋值为a、b,代码第27行为区间加a[i]*b[i],代码第29行为区间求和。

要用线段树维护,就要维护长度LEN、a的区间和SA、b的区间和SB、a*b的区间和SAB、左端点为I(右端点为目前最右边)的区间和SI。

区间赋值为a 区间赋值为b 区间增加a[i]*b[i]
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 LEN
a 0 0 0 0 0 1 0 0 0 0 1 0 0 0 SA
0 0 1 0 0 b 0 0 0 0 0 0 1 0 0 SB
0 0 a 0 0 0 b 0 0 0 0 0 0 1 0 SAB
0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 SI

区间[x, y]赋值为a,对a的最大值区间和的影响是sa[x..y] = a*len;对a*b区间和的影响是sab[x..y] = a*sb[x..y],相当于左乘第一个矩阵。

区间[x, y]赋值为b,对b的最大值区间和的影响是sb[x..y] = b*len;对a*b区间和的影响是sab[x..y] = b*sa[x..y],相当于左乘第二个矩阵。

区间[x, y]分别加上a[i]*b[i],统计答案只对SI产生影响,在原来基础上增加sab[x..y]即可,相当于左乘第三个矩阵。

不管是区间赋值,还是区间增加,都可以转化为区间左乘一个矩阵,或者说区间打标记!

程序实现

矩阵优化:考虑到矩阵有很多0,a[i][k]为0第三重循环没必要继续;矩阵上三角全部为0,发现乘完之后还是0,也没必要循环进去。标记下方,我们可以用数组u标记,u为0无需下放标记。

(感谢huangjianheng提供思路与优化技巧)

About

坚决不Copy代码!

本文标签:,,,,,,,,,

报歉!评论已关闭.