自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:55:04，当前版本为作者最后更新于2024-02-09 18:19:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathrm{\color{Black}B\color{Red}enq}$ 出的神奇倍增题。

对于这种细节很多的题，先把边界判掉。于是使用 lower_bound 把奶牛放到它第一个走到的交叉路口，再来考虑接下来的行走。

考虑奶牛的走法有什么规律或者性质。不妨设出发点 $(s_x,s_y)$ 满足 $(s_x+s_y)\bmod 2=0$；对于每条路，奶牛再它上面行走时会转向当且仅当遇到一条方向不同且奇偶性不同的路。由此可以确定的是，当奶牛再次走到与这条路方向相同的路时，不需考虑 $s_x+s_y$ 的奇偶性，下一条同方向的路的奇偶性一定与这条路相反。

于是这个东西可以倍增，类比 LCA 来理解，倍增的数组里面记的是“对于一条道路，令其‘父亲’为在它前面且与它奇偶性不同的第一条同方向道路，对于所有 $k$，这条路的 $2^k$ 级‘祖先’”；于是对于一个时间 $d$，就可以求出在 $d$ 秒内奶牛能走到的最远的交叉路口。

最后处理一下奶牛离开所有交叉路口后要走的路程即可。

时间复杂度 $O(n\log n)$。注意判断倍增的边界。

放代码：

/*
ID: CrowMatrix
TASK: Walking in Manhattan
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  vector<int> h,v;
  while(n--){
    char c; int x; cin>>c>>x;
    if(c=='H')h.emplace_back(x);
    else v.emplace_back(x);
  } // 存储所有道路
  sort(h.begin(),h.end());
  sort(v.begin(),v.end());
  h.emplace_back(2e9),v.emplace_back(2e9);
  vector r(h.size(),vector<int>(18)),
    c(v.size(),vector<int>(18)); // 倍增数组
  for(int i=0;i<18;i++){
    r[h.size()-1][i]=h.size()-1;
    c[v.size()-1][i]=v.size()-1;
  } // 倍增数组初始化
  for(int i=h.size()-2;~i;i--){
    r[i][0]=(h[i]+h[i+1]&1?i+1:r[i+1][0]);
    for(int j=1;j<18;j++)
      r[i][j]=r[r[i][j-1]][j-1];
  } // 对于横的道路处理 2^k 级祖先
  for(int i=v.size()-2;~i;i--){
    c[i][0]=(v[i]+v[i+1]&1?i+1:c[i+1][0]);
    for(int j=1;j<18;j++)
      c[i][j]=c[c[i][j-1]][j-1];
  } // 对于竖的道路处理 2^k 级祖先
  auto Q=[&](int x,int y,int d,int t=0){
    int h0=lower_bound(h.begin(),h.end(),y)-h.begin(),
      v0=lower_bound(v.begin(),v.end(),x)-v.begin();
    if(y<h[h0]){
      if(d+y<=h[h0])return make_pair(x,d+y);
      d-=h[h0]-y,t+=h[h0]-y;
    }
    if(x<v[v0]){
      if(d+x<=v[v0])return make_pair(x+d,y);
      d-=v[v0]-x,t+=v[v0]-x;
    } // 找到第一个交叉路口，记得判走不到的情况
    for(int k=17;~k;k--){
      int x=r[h0][k],y=c[v0][k];
      if(h[x]-h[h0]>d||v[y]-v[v0]>d)continue;
      if(v[y]-v[v0]+h[x]-h[h0]>d)continue;
      d-=v[y]-v[v0]+h[x]-h[h0],t+=v[y]-v[v0]+h[x]-h[h0];
      h0=x,v0=y;
    } // 倍增找走最远的点
    if(t&1){
      int a=c[v0][0];
      if(v[a]-v[v0]>=d)return make_pair(v[v0]+d,h[h0]);
      d-=v[a]-v[v0];
      return make_pair(v[a],h[h0]+d);
    }
    int a=r[h0][0];
    if(h[a]-h[h0]>=d)return make_pair(v[v0],h[h0]+d);
    d-=h[a]-h[h0];
    return make_pair(v[v0]+d,h[a]); // 最后一段
  };
  while(q--){
    int x,y,d; cin>>x>>y>>d;
    auto [a,b]=Q(x,y,d);
    cout<<a<<' '<<b<<'\n';
  } // 处理询问
  return 0;
}