# JOI2015/2016 春合宿 雇用計画(Employment)

バチャで解いた.
https://kenkoooo.com/atcoder/#/contest/show/172ff02f-aef7-48c8-8f65-0de9b8643797?activeTab=Standings

## 問題リンク
https://atcoder.jp/contests/joisc2016/tasks/joisc2016_d

## 解法

人$i$の評価値を$a_i$ とします.

### 小課題1(10点)
シュミレーションするだけです. クエリ1回あたり $O(N)$ にできます.
- 提出(10点):https://atcoder.jp/contests/joisc2016/submissions/47442464

### 小課題2(30点)
自分は少し本筋と逸れた方法で解きました. 満点解法とは関係ないので, 読み飛ばしても問題ないです.

評価の基準値$x$ をいろいろ試してみると, 以下のアルゴリズムが思いつきます.

1. クエリを先読みし, 評価の基準値の降順に並べておく.
2. 各時点における答えを表す $\text{cnt}$ を持っておく
3. 以下のようにして $a_i$ の降順に人$i$を追加しながら, 各クエリに対して答えを求めていく.
- $i$ の両隣がともに追加されていたら $\text{cnt}$ から $1$ 引く
- $i$ の両隣がどちらもまだ追加されていなければ $\text{cnt}$ に1加える

このアルゴリズムはソートがボトルネックになり, 計算量は $O(N\log N+M\log M)$ です

- 提出(40点): https://atcoder.jp/contests/joisc2016/submissions/47450477

ちなみに, このアルゴリズムは以下の問題の解法が元となっています.
:::spoiler ネタばれ防止
- JOI2018/2019 予選 日本沈没 https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d
:::

### 満点解法

解答クエリについて深掘りしていきます.

当然, 小課題1のように, 毎回調べていては間に合いません. かといって, 評価基準が毎回変わるので, セグメント木に特殊なモノイドを乗せてどうこうできる感じでもなさそうです.

グループに対応する"別の何か"を数えてみることにしましょう.

各グループに対して, 最も右にいる人に注目してみます. 最も右にいる人というのは1つのグループにつきちょうど1人なので, 答えはそのような人たちの人数に一致します.

グループが $a$ の区間になっていることに注目すると, 人 $i$ がグループの中で最も右にいるということは次のように言い換えることができます.

> 候補者 $i$ が採用されていて, かつ候補者 $i+1$ が採用されていない

すなわち,

> $a_i\geq x$ かつ $x\gt a_{i+1}$

です. したがって, 解答クエリで求めるべきはこれを満たすような $i$ の個数であるとわかります(ただし, $i=N$ の時は $a_{i+1}=a_{N+1}=-1$ とします).

以上の議論により以下の問題に帰着できました

> 数列 $a=(a_1,\dots,a_{N+1}=-1)$ に対して以下のクエリを処理せよ.
> - 解答クエリ:
> $x$ が与えられる. $a_i\geq x$ かつ $x\gt a_{i+1}$ を満たす $0\leq i\leq N$ の個数を求める.
>
> - 更新クエリ:
> $x,y$ が与えられる. $a_x\leftarrow y$ を行う.

この問題は, 以下で説明する $2$ 通りの解法により解けます.

なお, この問題では大小関係以外の情報は必要ありません.
したがって, 以下では評価値全てを座標圧縮して, **$N+M$ 以下の整数である**とします.

#### 解法1
上の問題は, 動的二次元BITにより解くことができます.

:::spoiler 動的二次元BITとは

二次元BITにおけるノードの追加を動的に行うようにしたものです.

以下のクエリを一回当たり $O(\log W\log H)$ で処理できます($W,H$ はそれぞれ$x,y$座標の最大値).

> 二次元平面上の各点に重みがついている. 最初はすべて重み$0$
> - Add($x, y, w$):
> 点 $(x,y)$ の重みに $w$ を加算する.
> ただし $0\leq x \lt W,0\leq y\lt H$
>
> - Sum($x_l, y_l, x_r, y_r$):
> 矩形領域 $[x_l, x_r)\times [y_l, y_r)$ に含まれる点の重みの総和を求める.
:::

上の問題に適応してみましょう.

各 $i$ について, 平面上の点 $P_i=(a_i,a_i+1)$ を考えてみます. すると, 解答クエリは以下のようになります.

> 矩形領域 $[x,N+M+1)\times[0,x)$ に含まれる $P_i$ の個数を求めよ.

これは$P_i$を動的二次元BITで管理しておけば答えられます.

以上より, $O((N+Q)(\log(N+Q))^2)$ でこの問題が解けました.

- 提出(100点, 3255 ms):
https://atcoder.jp/contests/joisc2016/submissions/47447998

logふたつなので, ある程度高速化しないと間に合わないかもしれません.

動的二次元BITはNyaanさんのものを使用させていただきました
- https://nyaannyaan.github.io/library/data-structure-2d/dynamic-binary-indexed-tree-2d.hpp

#### 解法2
動的二次元BITとかいうつよつよデータ構造を使わなくても解けます.

条件式の部分をぐっとにらんでみましょう.

> $a_i\geq x$ かつ $x\gt a_{i+1}\cdots(\ast)$

このままではどうこうできそうにないですね...
こういう時は否定をとってみましょう. ただし, 今回は両方とも否定をとってしまうと変化なしになってしまいます. 否定をとるのは片方だけにしておきましょう.

> $a_i\geq x$ かつ $a_{i+1}\geq x\cdots(\ast\ast)$

なんだかこれなら扱えそうです.

$(\ast)$ を満たす $i$ の個数は, $a_i\geq x$ を満たす $i$ の個数から $(\ast\ast)$ を満たす $i$ の個数を引けばよいです.

まず, $a_i\geq x$ を満たす $1\leq i\leq N$ の個数を求めます.
$f_j$ を $a_i=j$ を満たす $1\leq i\leq N$ の個数とします.すると, 求める値は $\sum_{j=x}^{N+M}{f_j}$ として求められます.したがって, $f$ をBinaryIndexTreeを用いて管理しておくことで, この値は $O(\log (N+M))$ で求められます.

次に, $(\ast\ast)$ を満たす $1\leq i\leq N$ の個数を求めます.
条件 $(\ast\ast)$ は, $\min(a_i,a_{i+1})\geq x$ と同値です. したがって, $b_i=\min(a_i,a_{i+1})$ という数列を考えて, $b$ に対応する先ほどの $f_j$ のような数列をBITで管理することで解くことができます.

解答, 更新 ともにクエリごと $O(\log (N+M))$ ですから, このアルゴリズムの計算量はは座標圧縮のソート部分がボトルネックとなり $O((N+M)\log (N+M))$ です. これなら十分間に合うでしょう.

- 提出(100点, 124ms) https://atcoder.jp/contests/joisc2016/submissions/47448272