简单?数据结构求助

学术版

ningago @ 2023-06-23 18:05:47

维护由带权区间构成的集合 S，维护操作：

  • 向 S 中插入区间 l_i,r_i，权值 a_i
  • 询问：\max_{l,r}\{\sum_{l\leq l_i\leq r_i\leq r}a_i\}

权值可负。

复杂度能做到多少啊QAQ

by Jorisy @ 2023-06-23 18:33:01

by chenxinyang2006 @ 2023-06-23 19:17:38

至少可以 rprmq2 吧，这个可以转化为维护 n \times n 矩阵，矩形加全局 \max

by chenxinyang2006 @ 2023-06-23 19:17:55

好像也不是至少，是等价

by ningago @ 2023-06-23 19:26:21

@chenxinyang2006

Ynoi/jk

应该是前缀矩形加吧，这样是不是能有其他性质/kk

by chenxinyang2006 @ 2023-06-23 19:38:15

@ningago rprmq2 不是前缀矩形加吗，主要任意矩形加可以容斥成四个前缀矩形……

by ningago @ 2023-06-23 19:42:12

awawawa

by 沉石鱼惊旋 @ 2023-06-25 21:00:45

@JYqwq 你怎么把我挂到学术版处刑了

|