警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

题意

传送门:洛谷 P2839 - middle

给一个序列,每次查询两个区间 \([a,b],[c,d]\),最大化 \(l\in[a,b],r\in[c,d]\) 时,区间 \([l,r]\) 的中位数。

集合 \(S\) 的中位数定义为 \(S\) 中第 \(\lfloor|S|/2\rfloor+1\) 小的数。

\(1\le n\le2\times10^4,1\le q\le25000,a<b<c<d\),强制在线。

阅读全文 »

题意

传送门:AGC031 E - Snuke the Phantom Thief

给你一个 \(n\) 个点的点集 \(S\),和 \(m\) 条限制,第 \(i\) 个点 \((x_i,y_i)\) 有一个权值 \(v_i\)。你要选出一个集合 \(T\subseteq S\),最大化 \(\sum_{i\in T}i_v\),且满足所有的限制。限制有四种:

  • L a b\(\sum_{i\in T}[x_i\le a]\le b\)
  • R a b\(\sum_{i\in T}[x_i\ge a]\le b\)
  • D a b\(\sum_{i\in T}[y_i\le a]\le b\)
  • U a b\(\sum_{i\in T}[y_i\ge a]\le b\)

\(1\le n\le80,1\le x_i,y_i\le100,1\le v_i\le10^{15},1\le m\le320,1\le a_i\le100,0\le b_i<n\),且 \((x_i,y_i),(t_i,a_i),(t_i,b_i)\) 互不相同。

阅读全文 »