Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

09/11
12:46
线段树

[bzoj 4491] 我也不知道题目名字是什么

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 给定一个序列A[i],每次询问l,r,求[l,r]内最长子串,使得该子串为不上升子串或不下降子串

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行n,表示A数组有多少元素
接下来一行为n个整数A[i]
接下来一个整数Q,表示询问数量
接下来Q行,每行2个整数l,r

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个询问,求[l,r]内最长子串,使得该子串为不上升子串或不下降子串

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6
6
5
6
4
//样例解释
五个询问分别对应
[1,6][1,6][2,6][1,6][6,9]

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

N,Q<=50000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

线段树模板题

维护取左边/右边的数和这个区间内最长不降/不升子串的长度

c++:

pascal:

 

[bzoj 4491] 我也不知道题目名字是什么