joisc2010 戦国時代(Sengoku)（難易度8）
解説
1人の見張りが見張れる範囲は下の図のようである。（問題文だけだと分かりにくいので）
将棋の角が動ける範囲と同じと捉えるといい。
https://gyazo.com/156a872fa61df1afca390c631f514625
こういう問題は45度回転して考えると良い。
ただ方法によっては実装が大変になるので、実装してて一番楽だった方法を紹介する。
45度回転してx軸とy軸をそれぞれ正方形の対角線と定めると、$ L = 5の時の各マスのx座標は下のようになる。（y座標も同様）
https://gyazo.com/3f30bfd625831af664f2904a55a79987
また、見張りの監視する範囲はx軸、y軸に平行になるので、まずはどの行・列が監視されているかをmap等で管理する（ACコードはvectorに入れてからstd::uniqueを使って重複を取り除いている）。
そして、監視している行・列に含まれるマスの個数を答えの変数に足す。ただ、この後に行・列の重複が重複しているマスを引かないといけない。ここからx軸とy軸を上のように定めた効果が出てくる。
x座標が$ iである行に対して、y座標が$ jである列が重複する条件は、実験してみると$ -(L - 1 - |i|) \leq j \leq L - 1 - |i|かつ$ jと$ L - 1 - |i|の偶奇が等しいことと分かる。
よって、監視している列を座標の偶奇で分けて、std::lower_boundやstd::upper_boundで二分探索をして上の条件を満たす$ jの個数を行ごとに数えればよい。
後は$ Lが割と大きいのでオーバーフローに注意。
感想
ずっと実装に困ってたけど、x軸とy軸の取り方を工夫したら簡単に実装出来て嬉しかった。