#E. [CZOJ 一周一测 R2 E] 美食诱惑 II

    传统题 1500ms 256MiB

[CZOJ 一周一测 R2 E] 美食诱惑 II

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

美食遍地,诱惑难抵。

题目描述

李劭鸿来到西伯利亚采购土豆来制作大波浪薯片。为符合大波浪薯片的气质,她每次会让你对战俘营农场进行采购,你要选出一个连续区间,使得这个区间里的土豆数量呈大波浪形状。你需要求出最长的区间长度。

有时候会出现丰收,即给出 L,R,ΔL,R,\Delta ,每个区间内的土豆数加上 Δ\Delta

形式化定义:给出每个农场的土豆数 ai(i[1,n])a_i (i\in[1,n]),每次询问最长的 rl+1([l,r][1,n])r-l+1([l,r]\subset[1,n]) 使得满足下列两条之一:

  • 要么 j[l,r]\forall j\in [l,r],如果 jj 是偶数则 aj1<aja_{j-1} < a_jaj>aj+1a_j > a_{j+1},如果 jj 是奇数则 aj1>aja_{j-1} > a_jaj<aj+1a_j < a_{j+1}
  • 要么 j[l,r]\forall j\in [l,r],如果 jj 是偶数则 aj1>aja_{j-1} > a_jaj<aj+1a_j < a_{j+1},如果 jj 是奇数则 aj1<aja_{j-1} < a_jaj>aj+1a_j > a_{j+1}

如果 j1j-1j+1j+1[l,r][l,r] 外则不考虑。

输入格式

整数 n,mn,m

nn 个正整数 aia_i

mm 行描述操作,先给出 opop

如果 op=1op=1 则输入 L,R,ΔL,R,\Delta,描述区间加,否则表示询问。

询问之间相互独立互不影响。

输出格式

对于 op=2op=2 输出答案

2 2
2 2
2
2
1
1

数据范围

对于 5%5 \% 的数据,0n,m<99824435300\leq n,m < 998244353^0

对于 20%20\% 的数据,0n,m5000\leq n,m\leq 500

对于 40%40\% 的数据,0n,m1040\leq n,m\leq 10^4

对于 70%70\% 的数据,0n,m1050\leq n,m\leq 10^5

对于 100%100\% 的数据,0n,m1060\leq n,m\leq 10^6

输入的其它数保证在 3232 位整数内。

[CZR-002] CZOJ Weekly Exercise Round 2

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-14 17:00
结束于
2023-7-14 22:00
持续时间
5 小时
主持人
参赛人数
30