このゲームに対して後退解析をかけることを考えます。一例として、サンプルを解析してみましょう。

• 初期状態: \([0,\infty)\)=引き分け
• 後手 \([1,2]\) : \([0,0]\) =先手勝ち、 \([1,\infty)\)=引き分け
• 先手 \([3,4]\) : \([0,2]\) =後手勝ち、 \([3,4]\)=先手勝ち、 \([5,\infty)\)=引き分け
• 後手 \([1,2]\) : \([0,0]\) =先手勝ち、 \([1,4]\)=後手勝ち、 \([5,5]\) =先手勝ち、 \([6,\infty)\)=引き分け
• 先手 \([1,3]\) : \([0,0]\) =後手勝ち、 \([1,3]\) =先手勝ち、 \([4,5]\)=後手勝ち、 \([6,8]\) =先手勝ち、 \([9,\infty)\)=引き分け

例えば先手が \([L,R]\) 個石を取るべき手番であったとすると、その手番を後退解析すると起こることは次の通りです。

• 山に残っている石の個数が \([0,L-1]\) 中なら後手勝ちとなる。
• 一手前の先手勝ち \([A,B]\) は \([A+L,B+R]\) に移る。ただし、この区間は複数重なりうる。
• 一手前の後手勝ち \([A,B]\) は \([A+R,B+L]\) に移る。ただし、この区間が潰れた場合は消滅する。

後手番についても同様のことが起こります。

また、どの時点でも区間を並べていったとき勝敗は

• …(先手勝ち)(後手勝ち)(先手勝ち)(引き分け)
• …(後手勝ち)(先手勝ち)(後手勝ち)(引き分け)

のどちらかの形を成します。要するに、引き分けを考えなかった場合はどちらが勝つかが交互に並ぶ構造になります。

この後退解析をデータ構造によって実現する方法を考えましょう。

まず、区間が潰れたり重なったりすることに目を瞑った時、片方の勝ちとなる全ての区間は長さ \(l\) だけ伸び、もう片方の勝ちとなる全ての区間は長さ \(l\) だけ縮みます。
愚直に処理をかけると区間の個数に対して線形時間かかってしまっていますが、「区間の長さに対応するオフセットを保持し、オフセットの基準値のみを加減する」という処理に置き換えると定数時間で処理を終えることができます。
さらに、この基準値を動かすタイミングでどの区間が潰れるかの把握も可能です。一連の操作は set や priority_queue 等を活用して実現可能です。

では、区間が潰れたり重なったりする場合を処理しましょう。
ある区間を潰す際、その両隣にどの区間があるかを把握したいです。これは連結リストの要領で行うと好都合です。また、勝敗の並びの構造から、ある区間を潰した際は(引き分けが絡まない限り)その両隣の区間がくっつくことも分かります。

あとはこの方針を実装に移すだけです。これ以上の詳細は複雑なので省略しますが、各区間の長さだけを保持し続けて、最後に具体的な石の個数を復元してからクエリに答えるという方針を取ると少し楽かもしれません。

この解法を用いると、この問題に時間計算量 \(O(N \log N)\) で正解できます。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

typedef struct{
  long long lef;
  long long rig;
}linknode;

linknode inil={-1,-1};

void shrink(long long tg,long long &llh,vector<linknode> &llis){
  long long le=llis[tg].lef;
  long long re=llis[tg].rig;
  if(le!=-1){llis[le].rig=re;}
  if(re!=-1){llis[re].lef=le;}
  if(tg==llh){
    llh=re;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  long long n;
  cin >> n;
  string s;
  // cin >> s;
  for(int i=0;i<n;i++){
    if(i%2==0){s.push_back('A');}
    else{s.push_back('B');}
  }
  vector<long long> l(n),r(n);
  for(long long i=0;i<n;i++){
    cin >> l[i] >> r[i];
  }

  long long ofs=0;
  vector<long long> ofsv(n);
  set<pl> sta,stb;
  long long llh=-1;
  vector<linknode> llis(n,inil);

  long long ls=0,rs=0;
  for(long long i=n-1;i>=0;i--){
    ls+=l[i]; rs+=r[i];
    if(i==0 || s[i]!=s[i-1]){
      if(s[i]=='A'){
        // shrink B win
        ofs+=(rs-ls);
        while(!stb.empty()){
          auto it=stb.begin();
          if((*it).first<ofs){
            pl od=(*it);
            stb.erase(it);
            long long le=llis[od.second].lef;
            long long re=llis[od.second].rig;
            if(le!=-1 && re!=-1){
              long long newg=(ofs-ofsv[le])+(ofs-ofsv[re])+2-(ofs-(*it).first);
              sta.erase({ofsv[le],le});
              sta.erase({ofsv[re],re});
              ofsv[le]=ofs-newg;
              sta.insert({ofsv[le],le});
              shrink(re,llh,llis);
            }
            shrink(od.second,llh,llis);
          }
          else{break;}
        }

        // add B win
        if(llh!=-1 && s[i]==s[llh]){
          stb.erase({ofsv[llh],llh});
          long long newg=(ls-1)+(ofsv[llh]-ofs)+1;
          ofsv[llh]=ofs+newg;
          stb.insert({ofsv[llh],llh});
        }
        else{
          ofsv[i]=ofs+(ls-1);
          llis[i].rig=llh;
          if(llh!=-1){llis[llh].lef=i;}
          llh=i;
          stb.insert({ofsv[i],i});
        }
      }
      else{
        // shrink A win
        ofs-=(rs-ls);
        while(!sta.empty()){
          auto it=sta.end();it--;
          if((*it).first>ofs){
            pl od=(*it);
            sta.erase(it);
            long long le=llis[od.second].lef;
            long long re=llis[od.second].rig;
            if(le!=-1 && re!=-1){
              long long newg=(ofsv[le]-ofs)+(ofsv[re]-ofs)+2-((*it).first-ofs);
              stb.erase({ofsv[le],le});
              stb.erase({ofsv[re],re});
              ofsv[le]=ofs+newg;
              stb.insert({ofsv[le],le});
              shrink(re,llh,llis);
            }
            shrink(od.second,llh,llis);
          }
          else{break;}
        }

        // add A win
        if(llh!=-1 && s[i]==s[llh]){
          sta.erase({ofsv[llh],llh});
          long long newg=(ls-1)+(ofs-ofsv[llh])+1;
          ofsv[llh]=ofs-newg;
          sta.insert({ofsv[llh],llh});
        }
        else{
          ofsv[i]=ofs-(ls-1);
          llis[i].rig=llh;
          if(llh!=-1){llis[llh].lef=i;}
          llh=i;
          sta.insert({ofsv[i],i});
        }
      }

      ls=0; rs=0;
    }
  }

  long long clef=0;
  set<pl> st;
  long long v=llh;
  while(v!=-1){
    if(s[v]=='A'){
      // cout << "B win " << ofsv[v]-ofs+1 << "\n";
      st.insert({clef,-1});
      clef+=(ofsv[v]-ofs+1);
    }
    else{
      // cout << "A win " << ofs-ofsv[v]+1 << "\n";
      st.insert({clef,1});
      clef+=(ofs-ofsv[v]+1);
    }
    v=llis[v].rig;
  }
  st.insert({clef,0});
  st.insert({8e18,0});

  long long q;
  cin >> q;
  while(q>0){
    q--;
    long long c;
    cin >> c;
    auto it=st.lower_bound({c,8e18}); it--;
    if((*it).second==1){cout << "Alice\n";}
    else if((*it).second==-1){cout << "Bob\n";}
    else{cout << "Draw\n";}
  }
  return 0;
}