Codechef January Challenge 2018 - Killing Monsters

問題

Contest Page | CodeChef

問題概要

モンスターが体いて、それぞれにからまでのIDが振られている。のIDを振られているモンスターは、はじめ体力がある。次のようなクエリが個来る：

• クエリ : k & x = kを満たすについて、のIDを振られているモンスターの体力を減少させる。

各クエリの終了時点で、生き残っている(体力が1以上)モンスターが何体いるかを答えよ。

• 
• 
• 
• 
• 

アイデア

クエリの性質上、クエリを区間に分割して高速化する、みたいなことは出来なさそう。そこで、今回は「クエリの平方分割」を行う。

まず、与えられる全クエリを時系列順でブロックに分ける(1ブロックの中に含まれるクエリは個)。

そして、そのブロックを順番に処理していく。あるブロックについて、そのブロック内のクエリをまとめて、それぞれのモンスターにどれくらいのダメージが入るのかを計算する。この計算にかかる計算量は、Segtreeの配列の構造をイメージすると、各段で右隣が左隣に足し込まれるイメージ(最上位ビットが0か1かの違いで、最上位ビットが1の方に入るダメージは0の方にも入る)を持つと、分割統治的に区間を伝播させることが出来るのでで処理ができる(実装も参照)。

そうすると、そのタイミングで死んでしまうモンスターが分かるので、そのモンスターに注目してそのブロック内のクエリをもう一度追いかけて、死ぬタイミングがちょうどどのクエリなのかを明らかにする。この操作には1モンスターに対してかかる。

以上のことをブロックごとにやっていくと、モンスターが死ぬタイミングのチェックはクエリ全体を処理する中で回だけ発生するので、全体としてで全ての処理が完了できる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int B = 600;
const int N = 1<<17;

// 累積ダメージ
ll d[N]={};
// ブロック内のダメージ
ll t[N]={};

// [l,r)の区間に伝播
void f(int l, int r){
    if(r-l==1) return;

    int m = (l+r)/2;
    f(l,m);
    f(m,r);

    // 最上位ビットが1のやつに入るダメージは最上位ビットが0でも入る
    rep(i,m-l) t[i+l] += t[i+m];
}

int main(){
    int n;
    cin >>n;
    vector<int> h(n);
    rep(i,n) cin >>h[i];

    int Q;
    cin >>Q;
    vector<int> x(Q),y(Q);
    rep(i,Q){
        cin >>x[i] >>y[i];
        x[i] &= (N-1);
    }

    vector<int> ans(Q);
    rep(i,B){
        if(B*i>=Q) break;
        fill(t,t+N,0);
        for(int j=B*i; j<min(B*(i+1),Q); ++j) t[x[j]] += y[j];

        f(0,N);

        vector<int> check;
        rep(j,n){
            // このブロック内で死ぬモンスター
            if(d[j]<h[j] && h[j]<=d[j]+t[j]) check.pb(j);
        }

        for(int j:check){
            ll dam = d[j];
            for(int k=B*i; k<min(B*(i+1),Q); ++k){
                if((j&x[k]) == j) dam += y[k];
                if(dam>=h[j]){
                    --ans[k];
                    break;
                }
            }
        }

        // 累積の方に渡す
        rep(j,n) d[j] += t[j];
    }

    ans[0] += n;
    for(int i=1; i<Q; ++i) ans[i] += ans[i-1];
    rep(i,Q) cout << ans[i] << endl;
    return 0;
}