[ABC186] F - Rook on Grid
[Q] https://atcoder.jp/contests/abc186/tasks/abc186_f
考察
1. 右下に移動した場合に、各列で何マスとるかを数列Dにすることはできる。
2. 下右に移動した場合に、各行で何マスとるかを数列Rにすることはできる。
3. 総和をとると、重複してカウントしてしまう。
4. 右下は全部加算するとして、下右のパターンで、増加分だけ加算したい。
5. 各行で0~rマスまで取るわけだけど、その中に自分のindexよりも小さいD[0] ~ D[r]の値の数が、増加分になる。
6. D[0] ~ D[r]の累積和はBITで管理すればいい。rは小さい値から挿入したい。
7. クエリ先読みをする
5 4 1
1 2
のとき注意。
5 0 0 0 // 5 0 5 5ではなく、5 0 0 0にする
1 x o x x
4 x x x x
4 x x x x
4 x x x x
4 x x x x
D[] = 5 0 0 0
R[] = 1 4 4 4 4
まずDを足す。
ans = 5 + 0 + 0 + 0
次にクエリ逆読み。Rについて、R[i]の小さい順に探索。{r, id}でsort。
0~rまで、BITにD[r]を加算していく。
そうすれば、ans += BIT.sum(id)が、Rの増加分となる。
ans = 17マス実装
// BIT
// 内部的にindexを+1して格納しているので注意
// https://atcoder.jp/contests/abc174/submissions/21572028
template<ll BT>
struct Bit
{
ll dat[BT+10]{};
void add(ll i, ll x){
++i;
for(; i<BT; i += i&-i) dat[i] += x;
}
ll sum(ll i){ // [0, i]
if (i<0) return 0;
if (i>=BT-1) i = BT-2;
++i;
ll res = 0;
for(; i>0; i -= i&-i) res += dat[i];
return res;
}
ll rangesum(ll L, ll R){ // [L, R]
return sum(R) - sum(L-1);
}
};
int main() {
cincout();
ll H, W, M;
cin >> H >> W >> M;
Bit<200020> bt;
vector<ll> D(W, H);
vector<ll> R(H, W);
rep(i, M){
ll y, x;
cin >> y >> x;
--y, --x;
chmin(R[y], x);
chmin(D[x], y);
}
vector<pll> Q; // rx, i
for(ll i = R[0] + 1; i < W; ++i){ // R[0]より先はとらない
D[i] = 0;
}
// クエリ先読み
rep(i, D[0]){ // D[0]までしか見ない。Hまで見ない。
Q.emplace_back(R[i], i);
}
sort(all(Q));
ll ans = 0;
rep(i, R[0]){ // R[0]までしか見ない。Wまで見ない。
ans += D[i];
}
ll st = 0;
rep(i, D[0]){ // D[0]までしか見ない。Hまで見ない
auto[r, id] = Q[i];
while(st < r){
bt.add(D[st], 1);
++st;
}
ans += bt.sum(id);
};
cout << ans << endl;
}Q. 方針見えたのに永遠にWA？
A. D[0]から先を見ないとか、R[0]以降の値を0にするとかを忘れた。